とある変人のお道具箱

技術系のことにについて幅広く触れていくブログです

【Python】 階乗、順列、組み合わせ

Python3のmathモジュールを利用すると階乗を計算することが可能です。この階乗を利用して順列や組み合わせの総数の計算をさせてみましょう。
また、順列や組み合わせを列挙したいときにはitertoolsモジュールを使いましょう。
   

   

階乗(math.factorial())

python3で階乗を計算するにはmathモジュール内のfactorial()関数を使います。

import math
print(math.factorial(5))   #120
#5! = 5*4*3*2*1 = 120

   

順列の総数を計算

順列の総数は以下の式で求められる

異なるn個のものからr個選んで一列に並べる場合の数
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の要素からなる長さrの配列(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)

   

組み合わせの総数を計算

異なるn個のものからr個選ぶ場合の数。順番は考慮しない。
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の要素からなる長さrの部分列を返します。

つまり、第一引数にイテラブル(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)