E-insight

How to properly implement shuffle May 17, 2010

I was challenged by a coworker to implement a shuffle function while playing a card game. Immediately, I thought of an algorithm that involves a random number generator. My algorithm loops through all n elements in the input. For each element, it ‘swaps’ itself with any other element in the sequenced input, the swapping index is determined by the random number generator. I thought this was a good approach, since the probability of any element been swapped and the position it swaps to is equal with respect to any other element. The method had turned out to be incorrect. The code illustrates my algorithm is as follows:

// my algorithm. Don't do this
public static void shuffle(List<Object> input) {
	Random rand = new Random();
	for (int i = 0; i < input.size(); i++) {
		Object tmp = input.elementAt(i);
		int index = rand.nextInt(input.size());
		input.setElement(i, input.elementAt(index));
		input.setElement(index, tmp);
	}
}

Close analysis reveals that this function is actually unfair generating random permutations. The number of possible permutations can be generated through shuffling n inputs is n!. But this function generates n^n arrangements. This means that there would be permutations appear more frequent than others.

I scratched my head (metaphorically) and wondered how Java std library did it. The source code of Collections.shuffle is as follows:

 // Java Standard Library, java.util.Collections.java. Use this.
 1845       /**
 1846        * Moves every element of the list to a random new position in the list.
 1847        *
 1848        * @param list
 1849        *            the List to shuffle.
 1850        *
 1851        * @throws UnsupportedOperationException
 1852        *             when replacing an element in the List is not supported.
 1853        */
 1854       public static void shuffle(List<?> list) {
 1855           shuffle(list, new Random());
 1856       }

...

 1858       /**
 1859        * Moves every element of the list to a random new position in the list
 1860        * using the specified random number generator.
 1861        *
 1862        * @param list
 1863        *            the list to shuffle.
 1864        * @param random
 1865        *            the random number generator.
 1866        * @throws UnsupportedOperationException
 1867        *             when replacing an element in the list is not supported.
 1868        */
 1869       public static void shuffle(List<?> list, Random random) {
 1870           @SuppressWarnings("unchecked") // we won't put foreign objects in
 1871           final List<Object> objectList = (List<Object>) list;
 1872
 1873           if (list instanceof RandomAccess) {
 1874               for (int i = objectList.size() - 1; i > 0; i--) {
 1875                   int index = random.nextInt(i + 1);
 1876                   objectList.set(index, objectList.set(i, objectList.get(index)));
 1877               }
 1878           } else {
 1879               Object[] array = objectList.toArray();
 1880               for (int i = array.length - 1; i > 0; i--) {
 1881                   int index = random.nextInt(i + 1);
 1882                   Object temp = array[i];
 1883                   array[i] = array[index];
 1884                   array[index] = temp;
 1885               }
 1886
 1887               int i = 0;
 1888               ListIterator<Object> it = objectList.listIterator();
 1889               while (it.hasNext()) {
 1890                   it.next();
 1891                   it.set(array[i++]);
 1892               }
 1893           }
 1894       }

This algorithm traverses the list from the end, each step it assumes that the elements visited are already shuffled, and thus not considered. The number of permutations generated by this algorithm is n!, exactly matches our mathematic model. I guess the lesson for me, and maybe the reader as well, is that never attempt to implement your own algorithm, because it’s very probable that your algorithm has been carefully implemented by other experts who had gone through the trouble of been criticized. At the same time, mistakes are avoided.