Shuffling Algorithm - Knuth Algorithm

You must be familiar how we shuffle a deck of card before start of any game. Its easy in real life to shuffle the deck of cards with hand.

How about in the online games? How would we shuffle a deck of card?

Shuffling should be done such that all the cards must be distributed uniformly i.e. every card should be distributed across the positions with equal probability. For the case of n items, all the items should be distributed with the probability of ${1 \over N}$.

Algorithm

1. We start by initializing $position = 0$.
2. Randomly pick an item from the array, range of the selection being $[position, N]$, where N = size of the array.
3. Swap the position of this random item with the item in the location $position$.
4. Increase $position$ by 1 and repeat from step 2 until $position == N$

Following this algorithm, it can be guaranteed that that each of the items in the array is uniformly distributed across the array with the probability of ${1 \over n}$.

$\def\specialFrac#1#2{\frac{x + #1}{y + #2}}$
• Probability of first item = $1 \over N$
• Probability of second item = $\textrm{probability of not being selected for first time} \times \textrm{probability of getting selected out of (N-1) items}$ = $\frac {N-1}{N} \times \frac {1}{N-1}$ = $\frac {1}{N}$
• Probability of third item = $\textrm{probability of not being selected for first time} \times \textrm{probability of not being selected for second time} \times$ $\textrm{probability of getting selected out of (N-2) items}$ = $\frac {N-1}{N} \times \frac {N-2}{N-1} \times \frac {1}{N-2}$ = $\frac {1}{N}$
• and so on...

So we can see that the probability of $\frac{1}{N}$ can be guaranteed for each of the items in the arra.

Implementation

	import java.util.Random;
	/**
	* This is a Shuffler class that can be used to shuffle given input array
	* uniformly
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class Shuffler {
	private Random random;
	/**
	* Constructor to Shuffler instance.
	* initializes the variable random
	*
	*/
	public Shuffler() {
	random = new Random();
	} // Shuffler
	//----------------------------------------------------------------------------
	/**
	* returns random number between two given range
	* @param lo lower limit of the range
	* @param hi upper limit of the range
	*/
	private int getRandom(int lo, int hi) {
	return random.nextInt(hi - lo + 1) + lo;
	} // getRandom
	//----------------------------------------------------------------------------
	/**
	* swaps two items in the given array
	* @param nums input array in which swapping will be done
	* @param i first index to swap
	* @param j second index to swap
	*/
	private void swap(int[] nums, int i, int j) {
	int temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
	} // swap
	//----------------------------------------------------------------------------
	/**
	* methods that shuffles the given array
	* @param nums array to shuffle
	*/
	public void shuffle(int[] nums) {
	for (int i = 0; i < nums.length - 1 ; i++ ) {
	int rand = getRandom(i, nums.length-1);
	swap(nums, i, rand);
	}
	} // shuffle
	//----------------------------------------------------------------------------
	/**
	* driver method
	*/
	public static void main(String[] args) {
	int[] nums = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
	Shuffler shuffler = new Shuffler();
	shuffler.shuffle(nums);
	for (int item : nums) {
	System.out.print(item + " ");
	}
	} // main
	//----------------------------------------------------------------------------
	} // Shuffler

view raw Shuffler.java hosted with ❤ by GitHub

Complexity

The algorithm shuffles the array in one pass and in place. So, the overall time complexity is $\cal{O(n)}$ and space complexity is $\cal{O(1)}$.

---

---

---