重複順列

重複順列について、写像とPythonを使って整理します。制約なしの重複順列や単射の順列は最も基本的な位置づけとなりますが、全射となると複雑な計算が必要になります。この考え方は包除原理といい、とても奥深いものがあります。

重複順列の考え方

重複順列（permutation with repetition）について理解するため、次の問題を考えます。

Example　1.1

5人の学生が合宿で2つの部屋に分かれて泊まることとします。各学生はどの部屋でも自由に選ぶことができるので、空き部屋ができることもあります。5人の学生は出席番号で表し、N={0, 1, 2, 3, 4}とします。また、部屋名はK={A, B}としたとき、部屋割りとして考えられる重複順列を生成し、その数を計算してください。

初歩的な問題ですが、写像の概念を使って整理していきます。

写像からみた重複順列

重複順列などの場合の数では、慣習的に定義域を集合 N 、終域を集合 K として、集合Nから集合Kへの写像と捉えます。Figure 1.1の１は、全員がAに泊まり$A=\{0, 1, 2, 3, 4\}$、$B$ には誰も泊まらず、$B=\emptyset$という極端な例、２は$A =\{0, 3\}$、$B=\{1, 2, 4\}$という通常考えられる部屋割りであることを示しています。

ここで次のものは写像になりません。

集合 $N$ の要素に対応する集合 $K$ の要素がない、つまり野宿はできないということです。
集合 $N$ の要素に対して集合 $K$ の中に対応する要素が複数ある、つまり部屋Aで騒いで部屋Bで寝るということはできません。

一方、全射や単射の制約がない写像の場合、次のものも許容されます。

1つの集合 $K$ の要素に対して複数の集合Nの要素が対応すること、つまり相部屋OKということです。
集合Kの要素の中に対応する要素がないこと、つまり空き部屋OKということです。上記のことから、重複順列は制約なし（unrestricted）の一般写像ということができます。

重複順列の生成と個数の計算方法

重複順列を生成する手順はFigure 1.3のように樹形図にすると理解しやすくなります。ちなみに、Figure 1.2の１、２という表記は、Figure 1.1の例に対応しています。

0がA,Bの2通りの部屋を選ぶことができ、その各々に対して1が2通り、さらにその各々について2が$2\times2=2^2=4$通り、というように0から4までの5人に対して繰り返すので、$2^5=32 $通りになるように、次の数式で計算することができます。

最終的には、図の右側のように５人がどの部屋に泊まるかを32個のタプルとして生成し、1つのリストとしてまとめます。このように、重複順列の数は $k^n$ （kのn乗）により計算することができるので、Pythonの標準モジュールには関数は用意されていません。この計算式は"k to the n-th power"と読みます。なお、$\prod$はproductの略号です。

Pythonによる重複順列の生成と個数の計算

Pythonの関数の分類

Pythonで使うことができる関数は次の4通りに分類されます。

1つ目は組み込み関数と呼ばれ、Pythonをインストールした時点で既に使える状態にあります。print()関数やlen()関数、input()関数などがこれにあたり、importも追加インストールも不要で、すぐに使うことができます。

2つ目は標準ライブラリにある関数で、同様にPythonをインストールした時点で既に使える状態にありますが、使用するためには、Pythonを起動するごとに明示的にインポートする必要があります。itertoolsモジュールやmathモジュールにある関数がその例で、組み込み関数に比べて使用する場面が限られているので、メモリ使用量や起動時間を抑えるため必要なときだけ読み込むようにしています。

3つ目は外部ライブラリにある関数で、Python本体には含まれず、pipコマンドなどにより追加でインストールし、その後Pythonを起動するごとにimport文を使って読み込む必要があります。数式処理や代数計算を行うSymPyや、科学技術計算に特化したSciPyなど多数あります。

4つ目は自作関数です。既存の機能では実現できない処理が必要な場合には、Pythonの機能を組み合わせて自分で関数を作成します。

このテキストでは、標準ライブラリと一般的に広く使われている外部ライブラリを合わせて「既存のライブラリ」と呼ぶことにします。

このテキストでは、写像に関わる様々な計算を既存のライブラリを使って実行し、その後で自作関数を作成して結果を照合し、正しく計算できているか確認します。さらに、既存のライブラリでは実現できない計算への応用も学んでいきます。

itertoolsモジュールのproduct関数による重複順列の生成

itertoolsモジュールのproduct関数を使うことにより重複順列を生成することができます。itertoolsモジュールはPythonの標準ライブラリのうちFunction Programming Moduleに分類されており、イテレータといわれるデータを1つずつ順番に取り出す機能が盛り込まれています。

product関数で重複順列を生成するときは、集合Nの要素数nを引数repeat=nとして渡します。戻り値として0,1,・・4が選んだ部屋がAかBかを表すイテレータが生成されます。

Code 1.1　itertoolsモジュールのproduct 関数による重複順列の生成

import itertools
k_list = ['A', 'B']
n = 5
itertools_product = itertools.product(k_list, repeat = n)
print(f'type of itertools_product = {type(itertools_product)}')
for product in itertools_product:
print(product)

type(itertools_product) = 
[('A', 'A', 'A', 'A', 'A'),
 ('A', 'A', 'A', 'A', 'B'),
（中略）
 ('A', 'B', 'B', 'A', 'A'),
 ('A', 'B’, 'B', 'A', 'B'),
（中略）
('B', 'B', 'B', 'B', 'A'),
('B', 'B', 'B', 'B', 'B')]

1.　product関数は標準ライブラリの1つであるitertoolsモジュールに含まれているので、使用するためにはPythonを起動するごとに1度だけインポートする必要があります。

4.　product関数でk_listのn回の直積を計算し、戻り値を変数itertools_productに代入します。

5.　product関数の型を出力します。itertools.product classという特殊な形式になります。

6.　forループを使ってitertools_productから要素を一つずつ順番に取り出し、print関数で出力しています。

itertools.product は、「イテレータ」と呼ばれる特別なデータ型で、データをあらかじめ全て主記憶領域（メモリ）に保存するのではなく、必要なときに1つずつ順番に作って処理し、使い終わったデータは消える仕組みです。このため、主記憶領域を無駄なく使えるという利点がありますが、再び同じデータを使うためには、もう一度最初から生成し直す必要があります。何度も参照する際にはlist関数を使い、リストに変換します。ここでは、変換したリストを使い、個数を計算します。

Code 1.2　イテレータをリストに変換し個数を数える

itertools_product_list = list(itertools.product(k_list, repeat = n))
print(
f'count of itertools.product ({len(k_list)}, {n}) : '
f'{len(itertools_product_list)}'
)

count of itertools.product (2, 5) : 32

2.　print関数の行が長くなる場合は、3行目から5行目まで行を分けます。

前に計算した$2^5=32 $通りと結果が一致しました。

重複順列を生成する自作関数

早速、重複順列を生成する関数を作成し、product関数と実行結果を比べます。

重複順列を生成する自作関数の流れ

この関数は、指定された要素リスト k_list に基づいて、長さ n の重複順列（順序付きの直積）を生成します。生成のために n 回ループを行い、各ステップで1つずつ要素を追加しながら順列を構築していきます。

たとえば k_list = ['A', 'B'] のとき、

1回目のループ後: [(A,), (B,)]

2回目のループ後: [(A, A), (A, B), (B, A), (B, B)]

3回目のループ後: [(A, A, A), (A, A, B), (A, B, A), (A, B, B), …]

というように、各ステップで要素が1つずつ増やします。

Figure 1.4は、2つ目の要素の生成が完了し、3回目のループの流れを示しています。

１　perm_list には前のステップで構築された部分的な順列（この時点では長さ2のタプル）が格納されています。それぞれを elm として1つずつ取り出します。各 elm に対して、k_list の各要素 item を末尾に追加し、next_perm に格納します。

２　全ての elm に対する処理が完了すると、next_perm には長さ3の順列がすべて揃うことになります。ここでnext_listをperm_listに代入します。

３　next_listを[]で初期化し、新しい順列群を次のステップに引き継ぎます。

４　以降のステップも同様に、perm_list から要素を取り出し、次の1文字を加える操作を繰り返していくことで、順列の長さを1つずつ延ばしていきます。

このように、順列の長さを1つ増やすたびに perm_list と next_perm を切り替えながら処理を続けるプログラムは次の通りです。perm_listだけで処理しようとすると、リスト読み出し中に同じリストへ要素追加という構造となり、無限ループの危険があります。

重複順列を生成する関数の作成

(1)の流れに沿って、重複順列を生成する関数を作成します。

Code 1.3　重複順列を生成する関数

def generate_unrestricted_perm(k_list, n):
perm_list = [()]
for _ in range(n):
next_perm = []
for elm in perm_list:
for item in k_list:
next_perm.append(elm + (item,))
perm_list = next_perm
return perm_list
unrestricted_perm_list = generate_unrestricted_perm(k_list, n)
print(
f'generate_unrestricted_perm({len(k_list)}, {n}) : '
f'{len(unrestricted_perm_list)}'
)

generate_unrestricted_perm(2, 5) : 32

2.　perm_listを初期化する際に、空のタプルを要素として持つリストとして定義します。4.でnext_permにコピーし、6.で制作途中の重複順列を読み込む際に何かしらのタプルがないとエラーになるためです。

3.　4.～8.により次のように、重複順列の作成途中のタプルを追加する処理をn回繰り返します。

8.　リストnext_permからこれまで作成した1つ1つの作成途中のタプルをelmとして取り出し、k_listから取り出したitemを右側に結合しperm_listに追加します。要素が1つだけのタプルは(item,)のようにかっこの中で変数にカンマを付けます。

2つのリストを使うので記憶領域が2倍必要になりますが、perm_listを読み込みながら、そのperm_listに複数の重複順列を追加すると、永久ループに陥る恐れがあります。このため、読み込み中のリストに要素を追加することは避けるのが原則です。前節の考え方に沿って、重複順列を生成する関数を作成します。関数名は制約なし(unrestricted)の順列(permutation)という意味でgenerate_unrestricted_perm関数とし、itertoolsと同様にk_listとnの2つの引数として渡します。なお、重複順列の各重複順列は、タプルにします。タプルはリストとは異なり、1度作ると変更することができません。このような性質をイミュータブル（変更不可）と呼び、ミュータブル（変更可能）であるリストよりも構造が単純であるため、マシンへの負荷が少なくなります。また、イミュータブルであることは不便なようにも思われますが、作成した配列を使っていろいろな処理をする場合、途中で勝手に変えられないので予測不能なエラーが発生するリスクが少なくなるというメリットもあります。

itertoolsのproduct関数と結果を比較

Code 1.2においてitertoolsのproduct関数で生成しリストに変換したunrestricted_perm_listと、Code 1.3において自作関数で生成したunrestricted_perm_listを比較し、一致していればその旨を表示します。

Code 1.4　 product関数と自作関数の結果を比較

if unrestricted_perm_list == itertools_product_list:
print('perm_unrestricted_list == itertools_product_list')

perm_unrestricted_list == itertools_product_list

1.　 2つのリストが示す重複順列は同じでも、並び順が異なると等しいと判断されません。この場合には、リストを並べ替えて比較し、等しくなれば重複順列は等しいと判断します。

ここでは、ソートをしなくても等しいと判断されました。両者とも同じ考え方でリストを生成していることが伺えます。

このことにより、perm_listが長さnの重複順列のリストとして返します。最終的にproduct関数の結果と一致します。作成の過程のリストをtempで仮置きして、perm_listと置き換えながら重複順列を生成するので、今一つ洗練されていない印象がありますが、これ以上シンプルなプログラムを作成するのは意外と困難です。

デカルト積を生成する関数

itertoolsによるデカルト積の計算

product 関数は、直積（デカルト積、cartesian product）を生成する関数で、2つ以上の集合の要素間で総当たりの組み合わせを生成します。例えば、洋服のタイプとして、T-Shirt, Sweaterがあり、それぞれにサイズと色があり、これらの全ての組み合わせがデカルト積になります。

デカルト積はitertoolsモジュールが提供するproduct関数により生成することができます。

Code 1.5　デカルト積を生成する関数

types = ['T-Shirt', 'Sweater']
sizes = ['L', 'M', 'S']
colors = ['Red', 'Blue', 'Green']
itertools_product = list(itertools.product(types, sizes, colors))
itertools_product

[('T-Shirt', 'L', 'Red'),
 ('T-Shirt', 'L', 'Blue'),
 ('T-Shirt', 'L', 'Green'),
 ('T-Shirt', 'M', 'Red'),
 ('T-Shirt', 'M', 'Blue'),
 ('T-Shirt', 'M', 'Green'),
 ('T-Shirt', 'S', 'Red'),
 ('T-Shirt', 'S', 'Blue'),
 ('T-Shirt', 'S', 'Green'),
 ('Sweater', 'L', 'Red'),
 ('Sweater', 'L', 'Blue'),
 ('Sweater', 'L', 'Green'),
 ('Sweater', 'M', 'Red'),
 ('Sweater', 'M', 'Blue'),
 ('Sweater', 'M', 'Green'),
 ('Sweater', 'S', 'Red'),
 ('Sweater', 'S', 'Blue'),
 ('Sweater', 'S', 'Green')]

4.　 types, sizes, colorsの3つのリストを引数として指定すると3つのリストの各要素の直積を生成することができます。

重複順列と同様にここでは k_list を5つの集合として捉え、直積を取るのでrepeat=5としています。その意味ではproduct関数の特殊な使い方といえます。

デカルト積を生成する関数を作成

itertoolsと同じようにデカルト積を計算する関数を作成します。ただし、Code 1.3と同じように、出力結果はリストにします。仮引数を*k_listというように*を付けると、複数のリストを指定することができます。関数名はgenerate_cartesian_productとし、同じ条件でデカルト積を生成し、product関数の出力結果と比較します。デカルト積では例のように2つ以上のリストについて計算する場合もあるので、リストの数が定まりません。この場合、仮引数に*を付け*k_listsとすると、引数の数を必要に応じて指定することができます。関数の中では*を取りk_listsをfor文で順次取り出し処理することができます。

Code 1.6　デカルト積を生成する関数

def generate_cartesian_product(*k_list):
perm_list = [()]
for current_list in k_list:
next_perm = []
for seq in perm_list:
for item in current_list:
next_perm.append(seq + (item,))
perm_list = next_perm
return perm_list
if itertools_product == generate_cartesian_product(types, sizes, colors):
print('itertools_product == generate_cartesian_product')

itertools_product == generate_cartesian_product

1.　引数は複数のリストという意味を込めて*klistsとします。

3.　k_listsからseqとしてリストを順次取り出します。　　

両者が一致していることを確認することができました。