Shuffle an array in place using the Knuth-Fisher-Yates algorithm.

fisher_yates.py

#!/usr/bin/env python
# -*- coding: utf-8 -*- 
#
# Shuffle an array in place using the Knuth-Fisher-Yates algorithm.

from random import randrange
 
def shuffle(x):
    """ Shuffle x in place using the Knuth-Fisher-Yates algorithm """
    for i in xrange(len(x)-1, 0, -1):
        j = randrange(i + 1)
        x[i], x[j] = x[j], x[i]



### testing
# this test takes some time (30 sec in my machine)!
def test_shuffle():
    """
    shuffle a three-card deck 6 000 000 times
    there are 3! = 6 possible combinations of the card. If the shuffle is 
    working properly, we should see each combination represented around 
    1 000 000 times.
    """
    from collections import Counter
    from numpy import allclose, array
    
    N = 6000000
    xinit = [str(i+1) for i in range(3)]
    sequenceCount = Counter()
    
    for i in range(N):
        shuffle(xinit)
        sequenceCount[''.join(xinit)] += 1
    
    assert allclose(array(sequenceCount.values())/float(N), 1./6, atol=1e-3)