順列の総数

順列の総数

　Python の標準ライブラリには 順列の総数 を返す関数が用意されていません。
　ただし、科学技術計算パッケージSciPy がインストールされていれば、サブパッケージの scipy.special.perm() を使って 順列 を計算できます (Anaconda には SciPy が付属しています)。

scipy.special.perm()

　scipy.special.perm(n, k) は n 個のものから k 個をとって並べる順列の総数を返します。5 個から 3 個をとって並べる順列の数を計算してみましょう。

# PYTHON_PERMUTATION_01

# In[1]

from scipy import special

# 5個から3個をとって並べる順列の数
p = special.perm(5, 3)

print(p)

60.0

　戻り値が float であることが気になるかもしれません。実は perm() の正式構文は

となっていて、オプション引数 exact で「処理時間が長くても正確な値を計算するかどうか」を選択します。デフォルトでは False となっているので、戻り値が非常に大きな値になる場合、引数 exact を省略すると処理が高速化される代わりに float 型の近似値が返されるようになっています。100 から 25 をとる順列の数を計算して比較してみます。

# In[2]

# 100個から25個をとって並べる順列の数
p1 = special.perm(100, 25)
p2 = special.perm(100, 25, exact=True)

print("exact=False:", p1)
print("exact=True:", p2)

exact=False: 3.761767332187389e+48
exact=True: 3761767332187389431968739190317715670695936000000

順列関数を自作する

　Scipy がインストールされていない場合、あるいはライブラリに依存したくない場合は自分で関数を実装します。順列を求める公式
　
\[{}_{n}\mathrm{P}_{k}=\frac{n!}{(n-k)!}\]
をそのまま適用するのであれば、階乗を計算する math.factorial() を使って簡単に実装できます。

# PYTHON_PERMUTATION_02

# In[1]

import math

# 順列の数を返す関数
def perm_test(n, k = 1):
    p = math.factorial(n) / math.factorial(n - k)
    return int(p)

x = perm_test(11, 4)

print(x)

7920

　ただし、この簡易的な実装では、大きな n が渡されたときに OverflowError が発生してしまいます。このエラーは巨大数による除算に起因します。OverflowError とならない範囲の数が渡されたとしても、階乗を階乗で割るという計算は無駄が多すぎます。また、mathモジュールのインポートが前提となっているので使い勝手もよくありません。そこで、組み込み型だけで関数を定義することを考えます。順列の総数の計算には
　
\[{}_{n}\mathrm{P}_{k}=n(n-1)(n-2)\ \cdots\ (n-k+1)\]
を使えば除算をしなくてすみます。これは普段、私たちが順列を
　
\[{}_{7}\mathrm{P}_{3}=7\cdot 6\cdot 5\]
のように計算しているのと同じやり方です。このような計算を行なう場合、for構文のイテラブルオブジェクトに range() を使います。

# In[2]

# n個からk個をとって並べる順列の数
# kを省略するとn!を計算
def perm(n, k = 1):
    pdt = 1
    if n != int(n) or k != int(k):
        raise ValueError("perm() not defined for float object")
    elif k < 0:
        pdt = 0
    elif n < 0:
        pdt = 0
    else:
        for x in range(n, n-k, -1):
            pdt *= x
    return pdt

print(perm(100,25))

3761767332187389431968739190317715670695936000000

　perm(n, k) は引数が渡されるとすぐに、n, k が 整数であるかをチェックして、非整数に対しては ValueError を発生させます。また、k の値はオプション引数としてあります。省略すると k = 1 が指定されたとみなされ、n! を計算します。
　

順列と重複順列

　itertools モジュールの itertools.permutations() で順列、itertools.product() で重複順列を計算できます。

itertools.permutations()

　itertools.permutations() は順列を イテレータ として生成します (順列の総数ではなく、条件を満たす組を全て返すということです)。

　引数 r で順列の長さを指定します (${}_{n}\mathrm{P}_{r}$ の $r$ です）。

# PYTHON_PERMUTATION_03

# In[1]

from itertools import permutations

my_list = ["a", "b", "c"]

# a, b, c の 3 個を 2 個並べる順列
x = permutations(my_list, 2)

print(list(x))

[('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'b')]

　引数 r を省略すると第 1 引数で渡されたイテラブルオブジェクトの長さが指定されたことになります。

# In[2]

my_list = ["a", "b", "c"]

# a, b, c の 3 個を 3 個並べる順列
x = permutations(my_list)

print(list(x))

[('a', 'b', 'c'), ('a', 'c', 'b'), ('b', 'a', 'c'),
('b', 'c', 'a'), ('c', 'a', 'b'), ('c', 'b', 'a')]

itertools.product()

　itertools.product() を使うと、重複順列を生成できます。戻り値はイテレータです。たとえば、red と blue から重複を許して3個並べる順列のイテレータは次のように生成します。

# PYTHON_PERMUTATION_04

# In[1]

import itertools
import pprint

colors = ["red", "blue"]

# redとblueから重複を許して3個並べる順列のイテレータ
h = itertools.product(colors, repeat=3)

　イテレータを list() に渡すと、イテレータの要素がすべて展開されます。ただし、展開するとイテレータは空になってしまうので、リストは変数に格納しておきます。

# In[2]

# イテレータの要素をリストに展開
list_h = list(h)

# 重複順列を表示
pprint.pprint(list_h)

[('red', 'red', 'red'),
 ('red', 'red', 'blue'),
 ('red', 'blue', 'red'),
 ('red', 'blue', 'blue'),
 ('blue', 'red', 'red'),
 ('blue', 'red', 'blue'),
 ('blue', 'blue', 'red'),
 ('blue', 'blue', 'blue')]

　展開したリストを len() に渡せば、重複順列の総数を取得できます。

# In[3]

# 重複順列の総数
n = len(list_h)

print(n)

8