静かなる名辞

pythonとプログラミングのこと

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

 順列(Permutation)と組み合わせ(Combination)がほしくなるときがある。

 だいたい標準モジュールかライブラリでできるので、計算方法についてまとめておく。

 目次

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

 つまり"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

 もうちょっと工夫して無駄な階乗を計算せずに済ませることもできる(分子分母で重複する部分を消す。手計算でやるときと一緒)。

 が、それにpythonのリスト処理を使ってしまうと速くなる保証はどこにもないし、ならnumpy+cythonで・・・と大げさなことを考えても、次に述べるライブラリでできる以上、やる必要もないのだった。

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

ライブラリを使う(おすすめ)

 scipyにある。

scipy.special.perm — SciPy v0.14.0 Reference Guide

scipy.special.comb — SciPy v0.14.0 Reference Guide

scipy.misc.comb — SciPy v0.18.1 Reference Guide

 順列(Permutation)はscipy.special.permだけのようだが(見落としてなければ)、組み合わせ(Combination)はscipy.misc.combとscipy.special.combの二つがある。2つあるcombは見たところ同じもの。なんでこんなことになってるんだろう。

 とりあえずこの記事ではscipy.specialの方を使うことにする。注意点としては、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を使おう。*1

*1:つーか、scipyは色々あるのに、ドキュメントの検索のしづらさとgoogleの検索順位の低さで損してる気がする。