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)
#(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)