【python】順列・組み合わせを計算する方法

　Pythonで、順列（Permutation）と組み合わせ（Combination）がほしくなるときがある。また、順列・組み合わせの数がほしくなることもある。

　順列・組み合わせそのものはitertoolsで、その数はscipyで出せる。計算方法についてまとめておく。

　目次

スポンサーリンク

順列・組み合わせそのものがほしい場合

　つまり"abc"から2個取り出す→[["a","b"], ["b", "c"], ["a", "c"]]という結果を期待している場合。

　これは標準ライブラリのitertoolsでできる。

順列の場合

　itertools.permutationsを使う。

>>> from itertools import permutations
>>> list(permutations("abc", 2))
[('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]

組み合わせの場合

　itertools.combinationsを使う。

>>> from itertools import combinations
>>> list(combinations("abc", 2))
[('a', 'b'), ('a', 'c'), ('b', 'c')]

　極めて容易。

順列・組み合わせの数だけほしい場合

　順列・組み合わせの数がほしいときもある。つまりnPrとnCrである。数字がほしいだけで、結果そのものは要らないケース。

　困ったことに、直接これを計算してくれる関数はmathモジュールなどには用意されていないようだ。実現する方法は何通りかある。

itertoolsの関数の結果をlen()する

　安直。パフォーマンス上はよくないだろうし、無駄っぽい。が、一応できる。

>>> from itertools import permutations
>>> from itertools import combinations
>>> len(list(permutations("abc", 2)))
6
>>> len(list(combinations("abc",2)))
3

　まあ、他の方法を使った方が良さげ。

自分で実装する

　数学的定義通り書くことができる。

>>> def P(n, r):
...     return math.factorial(n)//math.factorial(n-r)
... 
>>> def C(n, r):
...     return P(n, r)//math.factorial(r)
... 
>>> P(3, 2)
6
>>> C(3, 2)
3

　もうちょっと工夫して、無駄な階乗の計算を端折ることも考えられる。ただ、あまりごちゃごちゃ書くのも大変だし、実はscipyにあるので車輪の再発明をする必要すらない。

　nPrとかnCrを自分で実装している人は、素直にライブラリを使いましょう。

ライブラリを使う（おすすめ）

　scipyにある。どちらもscipy.specialから使える。

scipy.special.perm — SciPy v1.3.0 Reference Guide

scipy.special.comb — SciPy v1.3.0 Reference Guide

　注意点としては、exact=Trueを指定しないとfloatで近似値が返されること。この機能は近似値の方が便利/それで十分という用途では活用すれば良いと思う（ちなみにデフォルトはFalse。なので正確な値がほしいときは一々指定してやる必要がある）。

　あと、使い方はいまいちよくわからないけどndarrayも渡せるし、組み合わせの方はrepetitionオプションで重複ありの組み合わせも計算できる。

>>> from scipy.special import perm, comb
>>> perm(3, 2, exact=True)
6
>>> comb(3, 2, exact=True)
3

　あっさりしたものですね。

まとめ

　順列・組み合わせそのものがほしいときはitertools、順列・組み合わせの数がほしいときはscipyを使おう。
（余談だが、scipyは色々あって便利なのに、ドキュメントの検索のしづらさとgoogleの検索順位の低さで損してる気がする。）