Pythonで階乗、順列・組み合わせを計算、生成

Pythonの数学関数の標準モジュールmathを使うと階乗を計算できます。これを利用して順列・組み合わせの総数を算出できます。 また、itertoolsモジュールを使うとリスト(配列)などから順列・組み合わせを生成して列挙することができます。 ここでは、

階乗: math.factorial() 順列の総数を算出 リストから順列を生成、列挙: itertools.permutations() 組み合わせの総数を算出 リストから組み合わせを生成、列挙: itertools.combinations() 重複組み合わせの総数を算出 リストから重複組み合わせを生成、列挙: itertools.combinations_with_replacement()

および、順列を活用した例として、

文字列からアナグラムを作成

について、サンプルコードとともに説明します。 なお、単独のリストの要素の組み合わせではなく、複数のリストの要素の組み合わせを生成したい場合はitertoolsモジュールのitertools.product()を使います。

階乗: math.factorial()

mathモジュールに階乗を返す関数factorial()が用意されています。

9.2. math.factorial() — 数学関数 — Python 3.6.5 ドキュメント

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1

非整数値、負の値はエラーValueErrorになります。

# print(math.factorial(1.5))
# ValueError: factorial() only accepts integral values

# print(math.factorial(-1))
# ValueError: factorial() not defined for negative values

順列の総数を算出

順列は、異なるn個のものからr個選んで一列に並べる場合の数。 順列の総数は以下の式で求められます。

p = n! / (n - r)!

階乗を返す関数math.factorial()を使って以下のように算出できます。

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

print(permutations_count(4, 2))
# 12

print(permutations_count(4, 4))
# 24

整数int型を返すように、整数乗算を行う//演算子を用いています。

リストから順列を生成、列挙: itertools.permutations()

総数だけでなく、リスト(配列)などから順列を生成して列挙することもできます。 itertoolsモジュールのpermutations()関数を使います。

10.1. itertools.permutations() — 効率的なループ実行のためのイテレータ生成関数 — Python 3.6.5 ドキュメント

第一引数にイテラブル(リストや集合set型)、第二引数に選択する個数を渡すと、その順列のイテレータを返します。

import itertools

l = ['a', 'b', 'c', 'd']

p = itertools.permutations(l, 2)

print(type(p))
# <class 'itertools.permutations'>

すべて列挙するにはforループでまわせば問題ありません。

for v in itertools.permutations(l, 2):
    print(v)
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'a')
# ('b', 'c')
# ('b', 'd')
# ('c', 'a')
# ('c', 'b')
# ('c', 'd')
# ('d', 'a')
# ('d', 'b')
# ('d', 'c')

有限個のイテレータなので、list()でリスト型に変換することもできます。 リストの要素数をlen()で取得すると、階乗から算出した順列の総数と一致していることが確認できます。

p_list = list(itertools.permutations(l, 2))

print(p_list)
# [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'a'), ('b', 'c'), ('b', 'd'), ('c', 'a'), ('c', 'b'), ('c', 'd'), ('d', 'a'), ('d', 'b'), ('d', 'c')]

print(len(p_list))
# 12

第二引数を省略すると、すべての要素を選択する場合の順列が返されます。

for v in itertools.permutations(l):
    print(v)
# ('a', 'b', 'c', 'd')
# ('a', 'b', 'd', 'c')
# ('a', 'c', 'b', 'd')
# ('a', 'c', 'd', 'b')
# ('a', 'd', 'b', 'c')
# ('a', 'd', 'c', 'b')
# ('b', 'a', 'c', 'd')
# ('b', 'a', 'd', 'c')
# ('b', 'c', 'a', 'd')
# ('b', 'c', 'd', 'a')
# ('b', 'd', 'a', 'c')
# ('b', 'd', 'c', 'a')
# ('c', 'a', 'b', 'd')
# ('c', 'a', 'd', 'b')
# ('c', 'b', 'a', 'd')
# ('c', 'b', 'd', 'a')
# ('c', 'd', 'a', 'b')
# ('c', 'd', 'b', 'a')
# ('d', 'a', 'b', 'c')
# ('d', 'a', 'c', 'b')
# ('d', 'b', 'a', 'c')
# ('d', 'b', 'c', 'a')
# ('d', 'c', 'a', 'b')
# ('d', 'c', 'b', 'a')

print(len(list(itertools.permutations(l))))
# 24


itertools.permutations()では、要素が値ではなく位置に基づいて一意的に扱われる。値が重複していても特に考慮されません。
l = ['a', 'a']

for v in itertools.permutations(l, 2):
    print(v)
# ('a', 'a')
# ('a', 'a')

以下で説明する、

itertools.combinations()
itertools.combinations_with_replacement()

でも同じです。

組み合わせの総数を算出

組み合わせは、異なるn個のものからr個選ぶ場合の数。順列のように順番を考慮しない。 組み合わせの総数は以下の式で求められます。

c = n! / (r! * (n - r)!)

階乗を返す関数math.factorial()を使って以下のように算出できます。

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

print(combinations_count(4, 2))
# 6

整数int型を返すように、整数乗算を行う//演算子を用いています。

リストから組み合わせを生成、列挙: itertools.combinations()

総数だけでなく、リスト(配列)などからすべての組み合わせを生成して列挙することもできます。 itertoolsモジュールのcombinations()関数を使います。

10.1. itertools.combinations() — 効率的なループ実行のためのイテレータ生成関数 — Python 3.6.5 ドキュメント

第一引数にイテラブル(リストや集合set型)、第二引数に選択する個数を渡すと、その組み合わせのイテレータを返します。

l = ['a', 'b', 'c', 'd']

c = itertools.combinations(l, 2)

print(type(c))
# <class 'itertools.combinations'>

for v in itertools.combinations(l, 2):
    print(v)
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'c')
# ('b', 'd')
# ('c', 'd')

c_list = list(itertools.combinations(l, 2))

print(c_list)
# [('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]

print(len(c_list))
# 6

重複組み合わせの総数を算出

重複組み合わせは、異なるn個のものから重複を許してr個選ぶ場合の数。 重複組み合わせの総数は、異なるn + r - 1個のものからr個選ぶ組み合わせの数に等しい。 したがって、上で定義した組み合わせの総数を算出する関数を使えばよい。

def combinations_with_replacement_count(n, r):
    return combinations_count(n + r - 1, r)

print(combinations_with_replacement_count(4, 2))
# 10

リストから重複組み合わせを生成、列挙: itertools.combinations_with_replacement()

総数だけでなく、リスト(配列)などからすべての重複組み合わせを生成して列挙することもできます。 itertoolsモジュールのcombinations_with_replacement()関数を使います。

10.1. itertools.combinations_with_replacement() — 効率的なループ実行のためのイテレータ生成関数 — Python 3.6.5 ドキュメント

第一引数にイテラブル(リストや集合set型)、第二引数に選択する個数を渡すと、その重複組み合わせのイテレータを返します。

h = itertools.combinations_with_replacement(l, 2)

print(type(h))
# <class 'itertools.combinations_with_replacement'>

for v in itertools.combinations_with_replacement(l, 2):
    print(v)
# ('a', 'a')
# ('a', 'b')
# ('a', 'c')
# ('a', 'd')
# ('b', 'b')
# ('b', 'c')
# ('b', 'd')
# ('c', 'c')
# ('c', 'd')
# ('d', 'd')

h_list = list(itertools.combinations_with_replacement(l, 2))

print(h_list)
# [('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'b'), ('b', 'c'), ('b', 'd'), ('c', 'c'), ('c', 'd'), ('d', 'd')]

print(len(h_list))
# 10

文字列からアナグラムを作成

itertools.permutations()を使うと、文字列の並び替え(アナグラム)を簡単に作成できます。

s = 'arc'

for v in itertools.permutations(s):
    print(v)
# ('a', 'r', 'c')
# ('a', 'c', 'r')
# ('r', 'a', 'c')
# ('r', 'c', 'a')
# ('c', 'a', 'r')
# ('c', 'r', 'a')

一文字ずつのタプルを文字列に結合してリスト化するには以下のようにすればOKです。

anagram_list = [''.join(v) for v in itertools.permutations(s)]

print(anagram_list)
# ['arc', 'acr', 'rac', 'rca', 'car', 'cra']

リストやタプルの要素を文字列に連結するjoin()メソッドと、リスト内包表記を利用しています。

Last Updated: 6/26/2019, 10:34:03 PM