note.nkmk.me

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

Modified: | Tags: Python, 算数・数学

Pythonではmathモジュールを使って階乗や順列・組み合わせの総数を算出できる。SciPyでも順列・組み合わせの総数を算出する関数が提供されている。

また、itertoolsモジュールを使ってリストなどから順列・組み合わせを生成して列挙することも可能。

目次

なお、単独のリストの要素の組み合わせではなく、複数のリストの要素の組み合わせを生成したい場合はitertools.product()を使う。

階乗: math.factorial()

階乗を算出するにはmath.factorial()を使う。

import math

print(math.factorial(5))
# 120

print(math.factorial(0))
# 1
source: math_factorial.py

非整数値、負の値を指定するとエラーになる。

# print(math.factorial(1.5))
# TypeError: 'float' object cannot be interpreted as an integer

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

順列の総数を算出

順列は、異なるn個のものからk個選んで一列に並べる場合の数。

順列の総数pは階乗を使って以下の式で求められる。!は階乗を表す。

p = n! / (n - k)!

math.perm()

Python 3.8で順列の総数を返す関数math.perm()が追加された。

n個からk個選ぶとき、math.perm(n, k)と指定する。

import math

print(math.perm(4, 2))
# 12

print(math.perm(4, 4))
# 24
source: math_perm.py

非整数値、負の値を指定するとエラーになる。

# print(math.perm(4.5, 2.5))
# TypeError: 'float' object cannot be interpreted as an integer

# print(math.perm(-4, -2))
# ValueError: n must be a non-negative integer
source: math_perm.py

Python 3.7以前のバージョンでは、math.factorial()を使って以下のように算出できる。整数intを返すように、整数除算を行う//演算子を用いている。

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

print(permutations_count(4, 2))
# 12

print(permutations_count(4, 4))
# 24
source: math_factorial.py

scipy.special.perm()

SciPyにも順列の総数を返す関数scipy.special.perm()が用意されている。

n個からk個選ぶとき、scipy.special.perm(n, k)と指定する。

from scipy.special import perm

print(perm(4, 2))
# 12.0

print(perm(4, 2, exact=True))
# 12

print(perm(4, 4, exact=True))
# 24
source: scipy_special_perm.py

デフォルトは第三引数exact=Falseで、浮動小数点数floatが返される。整数intで取得したい場合はexact=Trueとする。

なお、import scipyだとscipy.specialモジュールは読み込まれないので注意。上の例のようにfrom scipy.special import permとしてperm()を実行するか、import scipy.specialとしてscipy.special.perm()を実行する。

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

リストなどから順列を生成して列挙するには、itertools.permutations()を使う。

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

import itertools

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

p = itertools.permutations(l, 2)
print(type(p))
# <class 'itertools.permutations'>
source: itertools_permutations_combinations.py

すべて列挙するには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')
source: itertools_permutations_combinations.py

list()でタプルを要素とするリストに変換できる。

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
source: itertools_permutations_combinations.py

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

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
source: itertools_permutations_combinations.py

itertools.permutations()では、要素が値ではなく位置に基づいて扱われる。値が重複していても特に考慮されない。

l = ['a', 'a']

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

以下で説明する、itertools.combinations(), combinations_with_replacement()でも同様。

組み合わせの総数を算出

組み合わせは、異なるn個のものからk個選ぶ場合の数。順列のように順番を考慮しない。

組み合わせの総数cは以下の式で求められる。二項係数とも呼ばれる。

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

math.comb()

Python 3.8で組み合わせの総数を返す関数math.comb()が追加された。

n個からk個選ぶとき、math.comb(n, k)と指定する。

import math

print(math.comb(4, 2))
# 6
source: math_comb.py

非整数値、負の値を指定するとエラーになる。

# print(math.comb(4.5, 2.5))
# TypeError: 'float' object cannot be interpreted as an integer

# print(math.comb(-4, -2))
# ValueError: n must be a non-negative integer
source: math_comb.py

Python 3.7以前のバージョンでは、math.factorial()を使って以下のように算出できる。整数intを返すように、整数除算を行う//演算子を用いている。

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

print(combinations_count(4, 2))
# 6
source: math_factorial.py

scipy.special.comb()

SciPyにも組み合わせの総数を返す関数scipy.special.comb()が用意されている。

from scipy.special import comb

print(comb(4, 2))
# 6.0

print(comb(4, 2, exact=True))
# 6

print(comb(4, 0, exact=True))
# 1
source: scipy_special_comb.py

scipy.special.perm()と同様に、デフォルトは第三引数exact=Falseで、浮動小数点数floatが返される。整数intで取得したい場合はexact=Trueとする。

第四引数repetitionで重複組み合わせの総数も取得可能。後述。

繰り返しになるが、import scipyだとscipy.specialモジュールは読み込まれないので注意。上の例のようにfrom scipy.special import combとしてcomb()を実行するか、import scipy.specialとしてscipy.special.comb()を実行する。

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

リストなどからすべての組み合わせを生成して列挙するには、itertools.combinations()を使う。

第一引数にイテラブル（リストや集合setなど）、第二引数に選択する個数を渡すと、その組み合わせのイテレータを返す。list()でリストに変換可能。

import itertools

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
source: itertools_permutations_combinations.py

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

重複組み合わせは、異なるn個のものから重複を許してk個選ぶ場合の数。

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

import math

def combinations_with_replacement_count(n, k):
    return math.comb(n + k - 1, k)

print(combinations_with_replacement_count(4, 2))
# 10
source: math_comb.py
def combinations_with_replacement_count(n, k):
    return combinations_count(n + k - 1, k)

print(combinations_with_replacement_count(4, 2))
# 10
source: math_factorial.py

上述のscipy.special.comb()では、第四引数repetition=Trueとすると重複組合せの総数が取得可能。

from scipy.special import comb

print(comb(4, 2, exact=True, repetition=True))
# 10
source: scipy_special_comb.py

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

リストなどからすべての重複組み合わせを生成して列挙するには、itertools.combinations_with_replacement()を使う。

第一引数にイテラブル（リストや集合setなど）、第二引数に選択する個数を渡すと、その重複組み合わせのイテレータを返す。list()でリストに変換可能。

import itertools

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

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
source: itertools_permutations_combinations.py

関連カテゴリー

関連記事