コンビネーションの計算

某IRCでコンビネーションの生成が遅いとの話題があったのでちょこっと作ってみた。yieldする関数に仕上げるのはまかせた

追記: 結局自分でやった。しかし要求されていた仕様とちがうってことがわかった！

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)]

整理する前のバージョン

In [2]: n = 3

In [3]: from operator import mul

In [4]: reduce(mul, [10 - i for i in range(n)])
Out[4]: 720

In [5]: [reduce(mul, [10 - i for i in range(m + 1)]) for m in range(n)]
Out[5]: [10, 90, 720]

In [6]: [reduce(mul, [10 - i for i in range(m)]) for m in range(n + 1)]
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/Users/nishio/cur/bitbucket/iqtest/<ipython console> in <module>()

TypeError: reduce() of empty sequence with no initial value

In [7]: [reduce(mul, [10 - i for i in range(m)], 1) for m in range(n + 1)]
Out[7]: [1, 10, 90, 720]

In [8]: N = 5

In [9]: [reduce(mul, [N - i for i in range(m)], 1) for m in range(n + 1)]
Out[9]: [1, 5, 20, 60]

In [10]: [[x % _[i + 1] / _[i] for i in range(n)] for x in range(_[-1])]
Out[10]: 
[[0, 0, 0],
 [1, 0, 0],
 [2, 0, 0],
 [3, 0, 0],
 [4, 0, 0],
 [0, 1, 0],
 [1, 1, 0],
 [2, 1, 0],
(以下略)