Problem

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

The Fisher-Yates shuffle algorithm, also known as the Knuth shuffle, is an algorithm for generating a random permutation of a finite sequence—in other words, for shuffling the sequence. The algorithm produces an unbiased permutation: every permutation is equally likely. The modern version of the Fisher-Yates shuffle, designed for computer use, was introduced by Richard Durstenfeld in 1964 and popularized by Donald E. Knuth.

We can think of deck of cards as the array of integers with indices lying from 0 to 51, as there are 52 cards.

Algorithm

Here’s a rundown of how the Fisher-Yates shuffle algorithm works:

  1. Start from the last element: Begin with the last element in the array (let’s call this array A) and the last element’s index n - 1, where n is the length of the array.
  2. Pick a random element: Select a random index j such that 0 <= j <= i where i starts at n - 1 and decreases by 1 in each iteration. A good pseudo-random number generator is used to ensure fairness.
  3. Swap elements: Swap the element at index i with the element at index j. If i is equal to j, the swap is essentially a no-op.
  4. Decrease i: Decrease i by 1 to move the “barrier” between the shuffled and unshuffled parts of the array. The elements from index i onwards are considered shuffled and are no longer touched.
  5. Repeat: Repeat the process of picking a random element and swapping until i reaches 0.

Pseudocode

function fisherYatesShuffle(A):
	n = length(A)
	for i from n - 1 downto 1 do
		j = random integer such that 0 ≤ j ≤ i
		swap A[i] with A[j]
	end for
end function
 
function swap(A, index1, index2):
    temp = A[index1]
	A[index1] = A[index2]
	A[index2] = temp
end function

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

Code

Java

Using Math.random()
public static void shuffleArray(int[] cards) {
	for (int i = cards.length - 1; i >= 0; i--) {
		int j = (int)(Math.random() * (i+1));
		swap(cards, i, j);
	}
}
Using rand.nextInt() 🥈
public static void shuffleArray(int[] cards) {
	Random rand = new Random();
	for (int i = cards.length - 1; i>0; i--) {
		int j = rand.nextInt(i+1);
		swap(cards, i, j);
	}
}

Code From Start of Array

The idea is to do several steps:

  1. Take i = 0 and then generate random index from [0, n-1] and swap these two elements.
  2. Take i = 1 and then generate random index from [1, n-1] and swap these two elements. …

Actually this code is for Fisher-Yates with indexes from lowest to highest, classical one is in opposite direction, but this one a bit easirer to code

Java

Using Math.random()
public static void shuffleArray(int[] cards) {
	for (int i = 0; i < cards.length; i++) {
		int j = (int)(Math.random() * (cards.length - i)) + i;
		swap(cards, i, j);
	}
}
Using rand.nextInt() 🥈
static void shuffle(int[] cards) {
	Random rand = new Random();
	for (int i = 0; i < cards.length; i++) {
		// Get a random index of the array past the current index.
		// The argument is an exclusive bound.
		// It will not go past the array send.
		int j = i + rand.nextInt(n - i);
		swap(cards, i, j);
	}
}

Dry Run

Dry Run for End of Array (Classic Fisher Yates)

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:

Dry Run From Start of Array

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]

Comparison with Reservoir Sampling

Fisher-Yates Shuffle vs Reservoir Sampling