How to shuffle a List

Question

I found this piece of Java code at Wikipedia that is supposed to shuffle an array in place:

public static void shuffle (int[] array)
{
    Random rng = new Random();
    int n = array.length;
    while (n > 1) 
    {
        n--;  
        int k = rng.nextInt(n + 1);
        int tmp = array[k];
        array[k] = array[n];
        array[n] = tmp;
    } 
}

Though I didn't test the code, it looks like it should work just fine with an array. In my C# project I created a CardSet class and used the above code in a Shuffle() method:

public class CardSet
{
    private List<Card> cards;

    public Card this[int i]
    {
        get {  return cards[i];  }
        set {  cards[i] = value;  }
    }

    public void Shuffle()
    {
        Random rng = new Random();
        int n = this.NumberOfCards;

        while (n < 1)
        {
            n--;
            int k = rng.Next(n + 1);
            Card tmp = this[k];
            this[k] = this[n];
            this[n] = tmp;
        }
    }

When I use the method, however, no shuffling happens:

CardSet cs = new CardSet();
cs.Shuffle(); 

foreach (Card c in cs)
{
    Console.WriteLine(c.ToString());
}

I just can't figure out why it doesn't work. I thought that the List might be automatically sorting its objects, so I tried changing one of its values,

cs[8] = new Card(Suites.Hearts, Numbers.Two);

and that Card was exactly where I put it. Either I made some simple mistake or I didn't write the shuffling algorithm correctly. If the code I supplied looks good and someone thinks the mistake might be somewhere else in my code, I can supply the rest of my code.

1) This shuffle function is very poor. 2) Why are you lifting such a simple method instead of writing your own? — Spencer Ruport, Aug 11 '09 at 19:50
@Spencer - It's always worth checking other peoples' solutions to a common problem even if you can easily roll your own. You might just learn something. The trick is being able to distinguish between good and bad implementations. — Dan Diplo, Aug 11 '09 at 19:55
I wanted to get a simple function working first. Next I think I'll try using either the RNGCrypoServiceProvider or the GUID from Fredou's link — golden_eagle, Aug 11 '09 at 19:57
Read this: http://www.codinghorror.com/blog/archives/001008.html — Lasse V. Karlsen, Aug 11 '09 at 19:59
@Spencer: The shuffle is not poor at all, it's actually the best method of shuffling a list that exists. It guarantees that each card have the same chance of ending up at each position in the deck, and it does it with the least possible amount of work. The only way to improve the algorithm is to use a random generator with better randomness. If you want a good algorithm, ask youself: WWKD (What Would Knuth Do). — Guffa, Aug 11 '09 at 20:13
This looks to be a Knuth-Fisher-Yate shuffle, which has no serious problems (assuming the PRNG is decent, which is a another story altogether). See Jeff Atwood's revelation on this: http://www.codinghorror.com/blog/archives/001015.html — Michael Burr, Aug 11 '09 at 20:37

score 16 · Accepted Answer · answered Aug 11 '09 at 19:50

16

Change

while (n < 1)

to

while (n > 1)

answered Aug 11 '09 at 19:50

Guffa

687,336
108
737
1,005

I should have caught that! Thanks – golden_eagle Aug 11 '09 at 19:54

score 3 · Answer 2 · answered Aug 11 '09 at 19:48

3

look into LINQ and orderby with a GUID

answered Aug 11 '09 at 19:48

Fredou

19,848
10
58
113

Cool, I like that :D, hopefully generating a GUID isn't painful in terms of performance but I think it is OK – bashmohandes Aug 11 '09 at 19:49
This is similar to how you (I) would shuffle a list in (MS)SQL (not sure about other flavors) SELECT * FROM Table ORDER BY newid() – Matt Kellogg Aug 11 '09 at 19:50
Using sorting to shuffle is not as good as the algorithm in the question. The range of random values is limited, which means that there is a chance that two cards will get the same random value, in which case they will not be randomly ordered. – Guffa Aug 11 '09 at 22:06
GUIDs are unique, not random. http://blogs.msdn.com/b/oldnewthing/archive/2012/05/23/10309199.aspx – Mark Sowul May 08 '13 at 03:12
@MarkSowul, what is the relevance of that statement for this question / solution? if you are commenting about Guffa comment, please specify it with (at)Guffa and don't downvote a working solution for it. – Fredou May 08 '13 at 10:39
Ordering by a GUID does not provide shuffling, because GUIDs are not random. A unique ascending number is a GUID and would not do any shuffling. See the post if you want more detail. – Mark Sowul May 08 '13 at 14:31

score 2 · Answer 3 · answered Aug 11 '09 at 19:53

2

Your while loop is off. It says while n is less than 1. You set n to the number of cards. So say if you have 52 cards n is definitely greater than 1 and your loop doesn't execute.

so change your while loop to look like this:

while(n > 1)

answered Aug 11 '09 at 19:53

scheibk

1,370
3
10
19

score 1 · Answer 4 · answered Aug 11 '09 at 19:53

The code in your example method and the code in your application (the first and second blocks) are different. In one, you use

While (n < 1)

And in the other you use

While (n > 1)

The correct one to use is in your sample - the "(n > 1)". If you use the other one, your loop doesn't execute even a single time - it skips over the condition and your deck is left untouched.

That said, LINQ is a better option if it's available to you.

How to shuffle a List

4 Answers4

Linked