I was asked by a colleague about how I might go about shuffling a deck of cards in C#. I found a few takes on this general problem on Google, and make no mistake: this has been covered by numerous persons over the last 80 years according to some of the research I found. So, yes, this is mostly likely a Wheel Version 2.0 piece of code, but here it is and hopefully it’ll be useful to someone.
Firstly, you need to decide on a Random Number Generator. If you’re just interested in solving this card-shuffling problem as part of a hobby-type application, using the System.Random class provided, or in my case the System.Security.Cryptography.RandomNumberGenerator, will suffice. To make this really strong, you may want to look at a pseudo-random algorithm along the lines of the Mersenne twister or one of it’s improved variants, or the simpler to implement Multiply-with-carry. Random number generators are really a topic all on their own and way out of the scope of this post.
Now, onto the relatively simple part: Shuffling a 52 card deck. I’ve designed a simple Deck class to make it easier for displaying results, but the algorithms can easily be transferred to whatever structure you’re using to store your cards/deck. I’ve also added my RNG as a static local variable to the class to increase its effectiveness. (Also, part of the RNG-related topic)
Expand Code public class Deck : IEnumerable<Deck.SuitCard>
{
public enum Suit { Spade, Diamond, Club, Heart }
public enum Card { A, N2, N3, N4, N5, N6, N7, N8, N9, N10, J, Q, K }
public class SuitCard
{
public long Index { get; set; }
public Card Card { get; set; }
public Suit Suit { get; set; }
public override string ToString()
{
return Card.ToString().Replace("N", "") + " " + Suit;
}
}
private readonly List<SuitCard> m_List = new List<SuitCard>();
private static readonly RandomNumberGenerator m_Random = RandomNumberGenerator.Create();
public Deck ()
{
int i = 0;
foreach (Suit suit in Enum.GetValues(typeof(Suit)))
{
foreach (Card card in Enum.GetValues(typeof(Card)))
{
m_List.Add(new SuitCard() { Card = card, Suit = suit, Index=i++ });
}
}
}
}
The first shuffle I’ve implemented is based on the Knuth-Fisher-Yates shuffle and as you can see by the code, is amazingly simple to implement.
Expand Code 1 public void Shuffle()
2 {
3 //Knuth-Fisher-Yates shuffle algorithm
4 for (int i = m_List.Count - 1; i > 0; i--)
5 {
6 var data = new byte[1];
7 m_Random.GetBytes(data);
8 Swap(i, data[0] % (i + 1));
9 }
10 }
11
12 private void Swap(int x, int y)
13 {
14 Debug.Assert(x >= y); //Just to make sure...
15 SuitCard tmp = m_List[x];
16 m_List[x] = m_List[y];
17 m_List[y] = tmp;
18 }
Quoted from Wikipedia: The basic process of Fisher–Yates shuffling is similar to randomly picking numbered tickets out of a hat, or cards from a deck, one after another until there are no more left. What the specific algorithm provides is a way of doing this numerically in an efficient and rigorous manner that, properly done, guarantees an unbiased result.
That being said, this computation as I’ve implemented in the source code is is prone to an effect known as modulo bias – you can seen the mod that is done on line 8.
Another amazingly clever, yet simple, method of shuffling the cards is randomising a number, assigning it to the first card in the deck, and repeating the process for each card. Once you’ve completed, you order the cards by the random number, and your deck is shuffled.
Expand Code 61 public void Shuffle()
62 {
63 for (int i = 0; i < m_List.Count; i++)
64 {
65 var data = new byte[4];
66 m_Random.GetBytes(data);
67 m_List[i].Index = data[0] + (data[1] * 256) + (data[2] * 65536) + (data[3] * 16777216);
68
69 }
70 m_List.Sort(new Comparison<SuitCard>(delegate(SuitCard x, SuitCard y)
71 {
72 if (x.Index < y.Index) return (-1);
73 if (x.Index > y.Index) return (1);
74 return 0;
75 }));
76 }
I use the same RNG, and then convert the four bytes to a long (line 67) – this is the field that I “sort” the deck by, to give you a shuffled deck.
And that’s my two ways of shuffling a deck of cards in C#.