階乗と順列

階乗と順列

階乗の計算

 mathモジュールの factorial(x) は x の 階乗 を返します。
 引数 x に非整数や負数を渡すと ValueError を返します。

# https://python.atelierkobato.com/permutation/

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

# 10の階乗を計算
a = math.factorial(10)

print(a)
3628800

 

順列の総数

Scipyパッケージを使って順列を計算します

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

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

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

# https://python.atelierkobato.com/permutation/

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

# https://python.atelierkobato.com/permutation/

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

# https://python.atelierkobato.com/permutation/

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

# https://python.atelierkobato.com/permutation/

# 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')]

 

# 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')]