Shuffle a deck of cards perfectly

Question

Write a method to shuffle a deck of cards. It must be a perfect shuffle – in other words, each 52! permutations of the deck has to be equally likely. Assume that you are given a random number generator which is perfect.

OR

How can you shuffle an array in O(n) time and O(1) space? For example, if input is an array of (1, 2, 3, 4, 5), one of the output can be (5, 4, 3, 2, 1) or (4, 2, 3, 1, 5).

Solution

This problem can be solved using Knuth Shuffling Algorithm a.k.a Fisher-Yates Shuffling Algorithm. We can think of deck of cards as the array of integers with indices lying from 0 to 51, as there are 52 cards.

The core strategy behind the algorithm is to pick a random index between 0 and N, where N is the greatest index of the unshuffled array, and then move that element to the shuffled part of the array. In other words, the algorithm partitions the original array into two parts, the unshuffled and shuffled part. It randomly picks an element from the unshuffled part and puts it into the shuffled part. It does that until no elements left in the unshuffled part.

How does random number generator works - in java or cpp? - you can check here.

Here is the implementation in C:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void knuthShuffle(int orgArray[], int arraySize)
{
   if (arraySize == 0 || arraySize == 1)
      return;

   srand(time(NULL));

   int i;
   int index, temp;
   for (i = arraySize - 1; i > 0; i--)
   {
      index = rand() % (i+1);
      temp = orgArray[index];
      orgArray[index] = orgArray[i];
      orgArray[i] = temp;
   }
}

Similar code in java:

public static void shuffleArray(int[] cards) {
    int temp, index;
    for (int i = 0; i < cards.length; i++) {
        index = (int) (Math.random() * (cards.length - i)) + i;
        temp = cards[i];
        cards[i] = cards[index];
        cards[index] = temp;
    }
}

Explanation: in order to partition the array, we traverse the array from the end to start. The subarray from iterator index i to the last index of the array (arraySize - 1) is the shuffled part. And, the subarray from the first index (0) to the iterator index i is the unshuffled part. As, the index i moves up the array, we randomly generate a number between 0 and i + 1 using C-function rand(). We then swap the element at the index that equals the random number with the element at the last index (i) of the unshuffled part. As the result of decreasing i by 1 for every loop iteration, the partitions are automatically reserved. Here is an example with illustration that will hopefully make everything clearer.

Example: we'll shuffle this array(1, 2, 3, 4, 5). Notice that the value for index is randomly picked, so at run time the algorithm may not generate the values in the exact order that they are here. We just need to understand that, the random values are always greater than or equal 0 and less than i. Here is what the array starts out with:

 

1.  First iteration, i = arraySize - 1 = 4. Let's say that index is randomly generated as 3, so we switch array[3] with array[4]. Here is the picture:

 

 2.  Second iteration, decrement i by 1, so i = 3 and index randomly generated as 0. We swap array[0] and array[3]:

 3.  Third iteration, i = 2 and index = 1. Swap array[2] with array[1].

4.   Fourth iteration, i = 1 and index = 0. Swap array[0] and array[1].
 

 5.  Fifth iteration: i = 0, so loop terminates. Nothing happens. Here is the final shuffled array:

Similarly example as per java
Let’s start with a brute force approach: we could randomly selecting items and put them into a new array. We must make sure that we don’t pick the same item twice though by somehow marking the node as dead.
Array: [1] [2] [3] [4] [5]
Randomly select 4: [4] [?] [?] [?] [?]
Mark element as dead: [1] [2] [3] [X] [5]


The tricky part is, how do we mark [4] as dead such that we prevent that element from being picked again? One way to do it is to swap the now-dead [4] with the first element in the array:


Array: [1] [2] [3] [4] [5]
Randomly select 4: [4] [?] [?] [?] [?]
Swap dead element: [X] [2] [3] [1] [5]


Array: [X] [2] [3] [1] [5]
Randomly select 3: [4] [3] [?] [?] [?]
Swap dead element: [X] [X] [2] [1] [5]


By doing it this way, it’s much easier for the algorithm to "know" that the first k elements are dead than that the third, fourth, nineth, etc elements are dead. We can also optimize this by merging the shuffled array and the original array.


Randomly select 4: [4] [2] [3] [1] [5]
Randomly select 3: [4] [3] [2] [1] [5]

References 

• http://tianrunhe.wordpress.com/2012/05/27/shuffle-a-deck-of-cards-perfectly/
• codesam