順列の総数

順列の総数

順列の総数

scipy.special.perm()

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

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

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

# 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() を使って簡単に実装できます(ただし後述するように、あまりおすすめできません)。

# 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関数を使います。

# 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モジュールには イテレータ を構築するための部品が揃っています。
 その中のひとつである permutations() は順列の数ではなく、順列そのものをイテレータとして生成します。

 itertools.permutations(iterable, r = None)

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

# PERMUTATION_04-1

# itertoolsモジュールからpermutations()をインポート
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')]

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

# PERMUTATION_04-2

# itertoolsモジュールからpermutations()をインポート
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')]