import random
from collections import defaultdict

def brodul_shuffle(deck):
    nCards = len(deck)
    for i in range(nCards):
        j = random.randrange(nCards)
        deck[i], deck[j] = deck[j], deck[i]

def python_shuffle(deck):
    random.shuffle(deck)

def shuffle(deck):
    # Knuth method
    n = len(deck)
    for i in range(n-1):
        j = random.randrange(i, n)
        deck[i], deck[j] = deck[j], deck[i]


def test_shuffler(shuffler, deck='abcd', n=10000):
    counts = defaultdict(int)
    for _ in range(n):
        input = list(deck)
        shuffler(input)
        counts[''.join(input)] += 1
    e = n*1./factorial(len(deck))  ## expected count
    ok = all((0.9 <= counts[item]/e <= 1.1) for item in counts)
    max_distance = max(counts[item]/e for item in counts)
    name = shuffler.__name__
    print '%s(%s) %s' % (name, deck, ('ok' if ok else '*** bad ***'))
    print 'max distance:', max_distance
    print '    ',
    # uncomment this to see distributions
    # for item, count in sorted(counts.items()):
    #     print "%s:%4.1f" % (item, count*100./n),
    print

def test_shufflers(shufflers=[shuffle, brodul_shuffle, python_shuffle], decks=['abcdef', 'abcde', 'abcd', 'abc','ab']):
    for deck in decks:
        print
        for f in shufflers:
            test_shuffler(f, deck)

def factorial(n): return 1 if (n <= 1) else n*factorial(n-1)

test_shufflers()