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.