順列の総数
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
【GPT講義】順列の総数を計算する手順
順列とは、ある集合から重複を許さずにいくつかの要素を選び、順序を考慮して並べる方法です。Pythonを用いて順列の総数を計算する手順を予備校スタイルで解説します。
問題文の読み取り: 与えられた問題文をよく読み、何を求められているのかを理解します。順列の総数を計算するためには、どの集合から要素を選ぶのか、いくつの要素を選ぶのかを確認します。
数値の確認: 問題文には具体的な数値が含まれている場合、それをメモしておきます。例えば、集合の要素数や選ぶ要素数などです。
順列の計算式の確認: 順列の総数を計算するためには、以下の順列の計算式を使います。
順列の総数 = n! / (n – r)!
ここで、nは集合の要素数、rは選ぶ要素数を示します。また、”!”は階乗を表します。
計算の実行: 上記の計算式を用いて、具体的な数値を代入して計算を実行します。Pythonでは、階乗の計算にはmath.factorial()関数を使用することができます。計算結果は整数として得られます。
計算結果の表示: 得られた順列の総数を適切な単位や形式で問題文に合わせて表示します。
確認とテスト: 計算が正しいかどうかを確認するために、手計算や別の方法で求めた結果と比較します。また、異なる入力値を用いて計算をテストし、正しい結果が得られることを確認します。
以上の手順に従って、Pythonを使用して順列の総数を計算することができます。必要に応じて、具体的な問題に合わせて計算を行ってください。
【GPT解説】Pythonのitertools.permutationsの高度な応用例
itertools.permutationsは、Pythonのitertoolsモジュールに含まれる関数で、与えられたイテラブルから順列を生成するためのツールです。ここでは、itertools.permutationsの高度な応用例をいくつか紹介します。
重複を許す順列の生成: 通常、itertools.permutationsは重複を許さない順列を生成しますが、場合によっては重複を許す順列が必要なこともあります。その場合、要素が重複する可能性を考慮して順列を生成することができます。
特定の条件を満たす順列の選別: 生成される順列の中から特定の条件を満たすものだけを抽出したい場合、生成された順列をフィルタリングすることができます。これによって、特定の条件を満たす順列のみを得ることができます。
順列の中から特定の順序パターンを抽出: 生成される順列の中から特定の順序パターンを抽出することができます。例えば、特定の要素が隣接しているかどうかを確認して、それに基づいて順列を選別することができます。
大規模な順列集合の処理: itertools.permutationsは生成される順列数が急速に増加するため、大規模な順列集合を処理する場合には注意が必要です。メモリ使用量や計算時間などの観点から、適切な手法を選択することが重要です。
順列生成の遅延評価: itertools.permutationsは遅延評価(lazy evaluation)をサポートしており、必要に応じて順列を逐次生成します。これによって、メモリを効率的に使用しながら大規模な順列集合を扱うことができます。
これらは、itertools.permutationsの高度な応用例の一部です。具体的な用途に応じて、適切な方法でitertools.permutationsを活用することが重要です。