Making a shuffle method

Question

i'm currently making a c# version of memory (the game), and I'm now at the point where I need to make a method that is shuffling my cards. I have something like this (but it isn't working yet):

    public void shuffle()
    {
        for (int i = 0; i < 100000; i++)
        {
            Random k = new Random();
            Random k2 = new Random();

            kaarten[k.Next(0, 11)] = kaarten[k2.Next(0,11)];
            kaarten[k2.Next(0, 11)] = kaarten[k.Next(0, 11)];
        }
    }

So i wondered if somebody could help me, thanks in advance! Steven.

Answer 1

Considering kaarten is a List of something that represents a card...

public void Shuffle()
{
    // Insert cards at random order into the shuffled list
    var shuffled = new List<Card>();
    var rand = new Random();

    // As long as there are any cards left to insert randomly
    while (kaarten.Count != 0)
    {
        // Get the index of the random card to insert
        var i = rand.Next(kaarten.Count);

        // Insert it
        shuffled.Add(kaarten[i]);

        // Remove from non-shuffled list
        kaarten.RemoveAt(i);
    }

    // Set the list of cards to the shuffled list
    kaarten = shuffled;
}

The problems with your current code:

You don't save the randoms into local variables, and so when you attempt to swap them, you really have 4 randoms, and not 2 randoms.

Also, for swapping two elements in an array you should use a tmp variable, as seen in a Swap algorithm almost any place you'd look.

For a complete shuffle, however, my approach loses the need of deciding how many times you loop over the swap for a sufficient shuffling, and is therefore more efficient as well more understandable.

There is another way to shuffle a list, which is a bit confusing (and least efficient) but shorter, if you prefer:

var rand = new Random();
kaarten = kaarten.Select(x => new{X=x,R=rand.Next()})
                 .OrderBy(x => x.R)
                 .Select(x => x.X)
                 .ToList();
                 //.ToArray(); if kaarten is an array and not a list

Answer 2

The first big problem with your code is that you're creating two instances of Random. The crappy seeding of new Random() means that those instances will most likely return exactly the same sequence.

new Random() seeds using Environment.TickCount, which only changes every few milliseconds. So if you create two instances of Random in quick succession, the time will be the same and thus they output the same sequence.

The proper solution is to create only one instance of Random at the beginning, and use if for all your randomness needs. Just be careful about multi-threading, instances of Random are not thread-safe.

Also note that the upper bound of random.Next is exclusive, so your code will work only on arrays with 11 elements. It's better to use the collection size instead of hardcoding the value.

Another problem with your code is that you didn't implement a proper swap. To swap you need to your swap has two issues: You're using new indices for the second direction, and you don't create a temporary copy in a local variable to avoid reading the overwritten value, instead of original one.

With these issues fixed your code looks like this:

Random random = new Random();//one persistent instance

public void shuffle()
{
    for (int i = 0; i < 100000; i++)
    {
        var i1=random.Next(kaarten.Count);
        var i2=random.Next(kaarten.Count);

        var temp=kaarten[i1];
        karten[i1]=kaarten[i2];
        karten[i2]=temp;
    }
}

That said, your approach is a bit inefficient, since you iterate 100000 times. The standard shuffling algorithm is a Fisher-Yates shuffle which Jon-Skeet describes at Is using Random and OrderBy a good shuffle algorithm?.

Answer 3

First, there's this handy extension method you can use, called Swap:

public static void Swap<T>(this IList<T> source, int one, int two)
{
    T temp = source[one];
    source[one] = source[two];
    source[two] = temp;
}

Now, your code should be easy:

public void Shuffle()
{
    int count = kaarten.Count;
    Random rnd = new Random();
    for (int i = 0; i < 1000; i++)
    {
        kaarten.Swap(rnd.Next(0, count), rnd.Next(0, count));
    }
}

Answer 4

it shuffles the arraylist elements

public void Shuffle(System.Collections.ArrayList elements)
    {
        int temp;
        Random randomNumber=new Random();
        for (int n = elements.Count; n > 1; )
        {
            int k = randomNumber.Next(n); //returning random number less than the value of 'n'
            --n; //decrease radom number generation area by 1 
            //swap the last and selected values
            temp = Convert.ToInt16(elements[n]);
            elements[n] = elements[k];
            elemetns[k] = temp;
        }
    }

Answer 5

Fisher–Yates shuffle

step 1. pull one card on random from the deck

step 2. place it in the new deck

step 3. if deck is not empty re-iterate 1 and 2

Add this to your class

public List<Card> Shuffle(List<Card> deck){
    List<Card> Shuffeled = new List<Card>();
    int deckSize = deck.Count;
    int selection = 0;
    Random rand = new Random();
    for(int i = 0; i < deckSize; i++){
        selection = rand.next(deck.Count-1);
        Shuffeled.Add(deck[selection]);
        deck.RemoveAt(selection);
    }
    return Shuffeled;
}

From your game call kaarten = Shuffle(kaarten);