Shuffling

Q: Given an array, print a random permutation of it such that each permutation is equally likely.

• The first approach is to use a random number generator to generate a value between 0 - 1 and associate each element of the array with a random value. Now sort the array based on these random values associated with the array elements.
• The second approach is to iterate over the array and swap the current element with another randomly selected element - Knuth-Fisher-Yates algorithm.
• Care should be taken so that we do not perform biased shuffle as explained in the following blog entry http://www.codinghorror.com/blog/2007/12/the-danger-of-naivete.html by Jeff Atwood

Java code for the second approach is given below. The biasedShuffle and knuthShuffle methods are called 100000 times each to gather statistics and to further corroborate the explanation by Jeff.

 

	/**
	* Author: Varun
	* Date: Jun 24, 2012
	*/
	import java.util.Random;
	public class ArrayShuffling {
	public static void biasedShuffle(int[] array) {
	Random r = new Random();
	for (int i = 0; i < array.length; i++) {
	int n = r.nextInt(array.length);
	int temp = array[n];
	array[n] = array[i];
	array[i] = temp;
	}
	}
	// similar implementation is used in Collections.shuffle
	public static void knuthShuffle(int[] array) {
	Random r = new Random();
	for (int i = array.length; i > 1; i--) {
	int n = r.nextInt(i);
	int temp = array[n];
	array[n] = array[i-1];
	array[i-1] = temp;
	}
	}
	public static int enumerateShuffledState(int[] shuffled) {
	if(shuffled.length != 3) {
	throw new IllegalArgumentException("Unsupported length: " +
	shuffled.length);
	}
	if(shuffled[0] == 0) {
	if(shuffled[1] == 1) {
	return 1;
	}
	return 2;
	} else if(shuffled[0] == 1) {
	if(shuffled[1] == 0) {
	return 3;
	}
	return 4;
	} else if(shuffled[0] == 2) {
	if(shuffled[1] == 0) {
	return 5;
	}
	return 6;
	}
	throw new IllegalArgumentException("Shuffled state is not " +
	"having values 0, 1 or 2");
	}
	public static void main(String args[]) {
	int[] array = new int[3];
	for(int i = 0; i < array.length; i++) {
	array[i] = i;
	}
	int[] shuffledStateCount = new int[6];
	for(int i = 0; i < 100000; i++) {
	int[] clone = array.clone();
	biasedShuffle(clone);
	shuffledStateCount[enumerateShuffledState(clone) - 1]++;
	}
	System.out.println("Biased shuffle statistics:-" );
	for(int i = 0; i < shuffledStateCount.length; i++) {
	System.out.println("Seq " + (i+1) + " count: " +
	shuffledStateCount[i]);
	}
	shuffledStateCount = new int[6];
	for(int i = 0; i < 100000; i++) {
	int[] clone = array.clone();
	knuthShuffle(clone);
	shuffledStateCount[enumerateShuffledState(clone) - 1]++;
	}
	System.out.println("Knuth shuffle statistics:-" );
	for(int i = 0; i < shuffledStateCount.length; i++) {
	System.out.println("Seq " + (i+1) + " count: " +
	shuffledStateCount[i]);
	}
	}
	}

view raw ArrayShuffling.java hosted with ❤ by GitHub