静かなる名辞

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

2019/03/22:TechAcademyがteratailの質問・回答を盗用していた件
2019/03/26:TechAcademy盗用事件 公式発表と深まる疑念


【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の検索順位の低さで損してる気がする。)