Python3のmathモジュールを利用すると階乗を計算することが可能です。この階乗を利用して順列や組み合わせの総数の計算をさせてみましょう。
また、順列や組み合わせを列挙したいときにはitertoolsモジュールを使いましょう。
階乗(math.factorial())
python3で階乗を計算するにはmathモジュール内のfactorial()関数を使います。
import math print(math.factorial(5)) #120 #5! = 5*4*3*2*1 = 120
順列の総数を計算
順列の総数は以下の式で求められる
異なるｎ個のものからｒ個選んで一列に並べる場合の数
p = n! / (n – r)!
よって、
import math def permutations_qty(n, r): p = int(math.factorial(n) / math.factorial(n - r)) return p print(permutations_qty(5,3)) #60 print(permutations_qty(5,5)) #120
順列を列挙
リストなどの配列から順列を生成し、全列挙することもできます。
itertoolsモジュール内のpermutations()関数を使います。
itertools.permutations(iterable,r=None)
iterableの要素からなる長さｒの配列(permutation)を連続的に返します。
つまり、第一引数にイテラブル（listやset）を、第二引数に選択する個数を与えるとその順列のイテレーターを返します。
すべてを列挙するにはfor文をまわしてやります。
import itertools elements = [1,2,3,4] for i in itertools.permutations(elements,2): print(i) #(1, 2) #(1, 3) #(1, 4) #(2, 1) #(2, 3) #(2, 4) #(3, 1) #(3, 2) #(3, 4) #(4, 1) #(4, 2) #(4, 3)
第二引数を省略するとすべての要素を選ぶ場合の順列が返ってきます。
for i in itertools.permutations(elements): print(i) #(1, 2, 3, 4) #(1, 2, 4, 3) #(1, 3, 2, 4) #(1, 3, 4, 2) #(1, 4, 2, 3) #(1, 4, 3, 2) #(2, 1, 3, 4) #(2, 1, 4, 3)<b><i>combinations()</i></b><b><i>combinations()</i></b> #(2, 3, 1, 4) #(2, 3, 4, 1) #(2, 4, 1, 3) #(2, 4, 3, 1) #(3, 1, 2, 4) #(3, 1, 4, 2) #(3, 2, 1, 4) #(3, 2, 4, 1) #(3, 4, 1, 2) #(3, 4, 2, 1) #(4, 1, 2, 3) #(4, 1, 3, 2) #(4, 2, 1, 3) #(4, 2, 3, 1) #(4, 3, 1, 2) #(4, 3, 2, 1)
組み合わせの総数を計算
異なるｎ個のものからｒ個選ぶ場合の数。順番は考慮しない。
c = n! / (r! * (n – r)! )
よって、
def combinations_qty(n, r): c = int(math.factorial(n) / (math.factorial(n - r) * math.factorial(r))) return c print(combinations_qty(5,2)) #10
組み合わせを列挙
itertoolsモジュールのcombinations()関数を使います。
itertools.combinations(iterable,r)
入力iterableの要素からなる長さｒの部分列を返します。
つまり、第一引数にイテラブル（listやset)を、第二引数に選択する個数を与えると、その組み合わせのイテレーターを返してくれます。列挙するにはfor文でまわしてやります。itertools.permutationsとほぼ同じですね。
import itertools elements = [1,2,3,4] for i in itertools.combinations(elements,2): print(i) #(1, 2) #(1, 3) #(1, 4) #(2, 3) #(2, 4) #(3, 4)
コメント