Script to test a few small numbers for a combinatorics problem

combos.py

"""Script to test a few small versions of combinatorics problem.

"""
from sys import stderr
from collections import Counter
from itertools import permutations
from math import factorial
from time import time

def answer(n, g):
    """Is this THE ANSWER???"""
    return factorial(n) / (factorial(n / g) * pow(factorial(g), n / g))

# N is number of cards, G is size of hand
N = 10
G = 5

# sanity check
if N % G:
    raise ValueError('n must be divisible by g')

# make the cards
cards = range(1, N + 1)

# this iterates over all n! permutations --- all possible ways of
# shuffling the deck
counter = Counter()
one_percent = factorial(N) / 100
start_time = time()
for permutation_index, permutation in enumerate(permutations(cards)):

    # just print something out to give a clue of how long this will take
    if not permutation_index % one_percent:
        print >> stderr, '%is\tabout %.0f%% done\t(%i of %i permutations)' % (
            time() - start_time,
            (permutation_index / one_percent),
            permutation_index,
            factorial(N),
        )

    # deal into (n / g) "hands"
    hands = [[] for hand in range(N / G)]
    for index, card in enumerate(permutation):
        hands[index % (N / G)].append(card)

    # sorted the hands to count *unique* configurations
    configuration = tuple(sorted(tuple(sorted(hand)) for hand in hands))
    counter[configuration] += 1

# the answer is the number of unique configurations
actual_answer = len(counter)

# are we right?
if len(counter) == answer(N, G):
    print 'hurray!'
    print len(counter)
else:
    print 'nope.'
    print len(counter), answer(N, G)