# macm.py from itertools import permutations # Returns the product of all the integers from begin to end, i.e. # begin * (begin + 1) * (begin + 2) * ... * end def product(begin, end): assert begin <= end return reduce(lambda x, y: x*y, xrange(begin, end+1)) # Returns the number of permutations of size r chosen from n distinct objects. def P(n, r): assert 0 <= r <= n return 1 if r == 0 else product(n-r+1, n) def P_test(): assert P(0, 0) == 1 assert P(1, 0) == 1 assert P(1, 1) == 1 assert P(2, 0) == 1 assert P(2, 1) == 2 assert P(2, 2) == 2 assert P(3, 0) == 1 assert P(3, 1) == 3 assert P(3, 2) == 6 assert P(3, 3) == 6 print 'All P(n,r) tests passed!' # Returns n!, i.e. 1*2*3*...*n. Note that 0!=1. def factorial(n): assert n >= 0 return P(n, n) # shorter name for factorial def fact(n): return factorial(n) def factorial_test(): assert factorial(0) == 1 assert factorial(1) == 1 assert factorial(2) == 1 * 2 assert factorial(3) == 1 * 2 * 3 assert factorial(4) == 1 * 2 * 3 * 4 assert factorial(5) == 1 * 2 * 3 * 4 * 5 print 'All factorial tests passed!' # prints all n! permutations of the numbers 1 to n # make sure n is not too big!! def print_perms(n): assert n > 0 if n > 10: print 'print_perms only works for 1 <= n <= 10' return items = [a for a in xrange(1, n+1)] for i,p in enumerate(permutations(items)): print '%s %s' % (p, i+1) # Returns the number of ways r things can be chosen from n objects, where the # order of the r things doesn't matter. def C(n, r): assert 0 <= r <= n return P(n, r) / factorial(r) def C_test(): assert C(0, 0) == 1 assert C(1, 0) == 1 assert C(1, 1) == 1 assert C(2, 0) == 1 assert C(2, 1) == 2 assert C(2, 2) == 1 assert C(3, 0) == 1 assert C(3, 1) == 3 assert C(3, 2) == 3 assert C(3, 3) == 1 print 'All C(n,r) tests passed!' if __name__ == '__main__': P_test() factorial_test() C_test()