順列の総数

順列の総数

順列の総数

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

scipy.special.perm()

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

scipy.special.perm(n, k, exact=False)

によって計算されます。オプション引数 exact で「処理時間が長くても正確な値を計算するかどうか」を選択します。デフォルトでは False となっているので、この引数を省略すると処理が高速化される代わりに戻り値は近似値となります。

# PYTHON_PERMUTATION_01

# Scipyパッケージのscipy.specialモジュールをインポート
from scipy import special

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

print("x =", x)
print("y =", y)
x = 60.0
y = 60

 

関数を自作して順列を計算する

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

# PYTHON_PERMUTATION_02

# mathモジュールをインポート
import math

# n個からk個をとって並べる順列の総数
def permtest(n, k = 1):
    p = math.factorial(n) / math.factorial(n - k)
    return int(p)

x = permtest(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() を使います。

# PYTHON_PERMUTATION_03

# 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(7,3))
210

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

順列と重複順列

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

itertools.permutations()

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

itertools.permutations(iterable, r=None)

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

# PYTHON_PERMUTATION_04-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 引数で渡されたイテラブルオブジェクトの長さが指定されたことになります。

# PYTHON_PERMUTATION_04-2

from itertools import permutations

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_05-1

import itertools
import pprint

colors = ["red", "blue"]

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

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

# PYTHON_PERMUTATION_05-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() に渡せば、重複順列の総数を取得できます。

# PYTHON_PERMUTATION_05-3

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

print(n)
8