Skip to content

Instantly share code, notes, and snippets.

@j-faria j-faria/fisher_yates.py
Last active Dec 25, 2015

Embed
What would you like to do?
Shuffle an array in place using the Knuth-Fisher-Yates algorithm.
#!/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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.