順列の総数

当サイトではアフィリエイトプログラムを利用して商品を紹介しています。

順列の総数

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

scipy.special.perm()

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

# PYTHON_PERMUTATION

# In[1]

from scipy import special

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

print(p)
# 60.0

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

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

となっていて、オプション引数 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() を使って簡単に実装できます。

# In[3]

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() は順列を イテレータ として生成します (順列の総数ではなく、条件を満たす組を全て返すということです)。

itertools.permutations(iterable, r=None)

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

# PYTHON_ITERTOOLS_PERMUTATION

# 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_ITERTOOLS_PRODUCT

# 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

コメント

  1. あとりえこばと より:

    【AI連載小説】科学とコードの交差点(31)「itertools.permutationsの計算速度に関する考察」
     
    ある日、六郷開誠と刑部明信は、京都大学のキャンパス内のカフェで再び集まりました。彼らは順列の計算方法についての話題で盛り上がっていました。
     
    「明信、前回の話の後、itertools.permutationsを使って順列の計算を試してみたんだ。確かに便利だったけど、計算速度についてはどうなんだろう?」
     
    「それはいい質問だね、開誠。itertools.permutationsは便利な反面、計算速度には注意が必要な場合もあるんだ。特に、要素数が増えると計算時間が指数関数的に増える可能性があるんだよ」
     
    「それはどうしてなんだ?」

    「itertools.permutationsは、与えられたリストの全ての順列を生成するために、ネストされたループを使用しています。つまり、要素数がnの場合、n個の要素の全ての組み合わせを生成するためにn回のループが必要になるんだ。そのため、要素数が増えると計算時間が指数関数的に増えることになるわけさ」
     
    「なるほど、つまり要素数が増えると計算時間が膨大になる可能性があるってことか。でも、順列の計算には他に効率的な方法はあるのかな?」
     
    「そうだね、開誠。もちろん他の方法もあるよ。例えば、要素数が比較的小さい場合は、再帰的なアルゴリズムを使って順列を生成する方法もあります。また、特定の制約条件がある場合には、順列を生成する代わりに直接必要な組み合わせを生成する方法も考えられるんだ」

    「なるほど、要素数や制約条件によって最適な方法が異なるんだね。それに応じて計算速度を考慮しながらアプローチを選ぶ必要があるってことか」
     
    「その通りだよ、開誠。計算速度はプログラムの実行時間やリソースの使用量に影響を与える重要な要素だからね。順列の計算の際には、要素数や制約条件を考慮しながら、最適なアルゴリズムや手法を選ぶことが大切なんだ」