コンビネーション

Python アルゴリズム

漸化式を利用したコンビネーションの計算

{}_n C_r = \frac{n-r+1}{r} {}_n C_{r-1}

#combi.py
#! usr/bin/env python
# -*- coding :utf-8 -*-
import sys

#calculate combination (n,r)
num = raw_input("Set n: ") 
repeated = raw_input("Set r: ")
if num < repeated:
    print "input error"
#Recurrence relation formula
combi = int(num) #initializiing
if repeated == 0:#definition of (n,0)
    combi = 1
for r in range(2,int(repeated)+1):
    combi = ((int(num)-r+1) * combi) / r
print "combination (n,r) =  ", combi


こうやるらしい。

from operator import mul
def perm(n, m):
    divs = [reduce(mul, [n - i for i in range(j)], 1) for j in range(m + 1)]
    total = divs[-1]
    for x in xrange(total):
        yield [x % divs[i + 1] / divs[i] for i in range(m)]

http://d.hatena.ne.jp/nishiohirokazu/20100317/1268824264