重複順列　N,Kラベルあり　単射　

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

重複順列の考え方

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

Example 1.1

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

やっていることは単純ですが、写像について理解するため少しまどろっこしい説明が必要になります。

写像からみた重複順列

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

Figure 1.1 写像で見る重複順列
Figure 1.1 写像で見る重複順列

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

一方、写像について全射や単射の制約なしの場合、次のものは問題ありません。

重複順列の生成と数の計算

重複順列の生成手順を図にすると次のようになります。

Figure 1.2 重複順列の生成の考え方
Figure 1.2 重複順列の生成の考え方

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

Equation 1.1 重複順列の個数

$_k\prod{_n}=k^n$

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

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

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

itertoolsモジュールのproduct関数を使うことにより重複順列を生成することができます。itertoolsモジュールはPythonのFunction Programming Moduleに分類されており、イテレータといわれるデータを1つずつ順番に取り出す機能が盛り込まれています。標準ライブラリの1つなので、Pythonがインストールされていれば使うことができます。ただし、ビルドイン関数ではないので、使用する都度、インポートする必要があります。

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

Code 1.1itertools モジュールによる重複順列のリストの生成

  1. import itertools
  2. k_list = ['A', 'B']
  3. itertools_product_list = list(itertools.product(k_list, repeat = 5))
  4. print('itertools product(2, 5) =',len(itertools_product_list))
  5. itertools_product_list
itertools product(2, 5) = 32
[('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')]

4.　イテレータで生成された重複分割をprint関数で出力するためには、list関数を使いリスト型に変換する必要があります。

product関数は、直積（デカルト積cartesian product）を生成する関数で、2つ以上の集合の要素間で総当たりの組み合わせを生成します。ここではk_list別々の5つの集合として捉え、直積を取るのでrepeat=5としています。その意味ではproduct関数の特殊な使い方といえます。

重複順列を生成する関数

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

図表2のような重複順列を配列perm_listに作成する場合、次の2つの考え方があります。

① n回forループを回し、perm_listに各人がどの部屋を選ぶかを順次追加

リストの幅を幅優先探索（BFS = Breadth-First Search）という方法です。

初期状態: 空の順列から始めます perm_list = [()]

これは、まだ何も選んでいない状態です

第1層の探索: 最初の位置に配置できる全ての要素（A, B）を追加します

perm_list = [(A,), (B,)]

この段階では、長さ1の可能な順列をすべて生成しました

第2層の探索: 第1層の各順列に対して、次の位置に配置できる全ての要素を追加します

(A,) から → (A,A), (A,B)

(B,) から → (B,A), (B,B)

結果: perm_list = [(A,A), (A,B), (B,A), (B,B)]

この段階では、長さ2の可能な順列をすべて生成しました

第3層の探索: 第2層の各順列に対して、次の位置に配置できる全ての要素を追加します

(A,A) から → (A,A,A), (A,A,B)

(A,B) から → (A,B,A), (A,B,B)

(B,A) から → (B,A,A), (B,A,B)

(B,B) から → (B,B,A), (B,B,B)

結果: perm_list = [(A,A,A), (A,A,B), (A,B,A), (A,B,B), (B,A,A), (B,A,B), (B,B,A), (B,B,B)]

・・

のように追加します。

② はじめに1つ重複分割を生成し、そこから要素を入れ替え

深さ優先探索（DFS = Depth-First Search）という方法です。

1つ目　(A, A, A, A, A)

2つ目　(A, A, A, A, B)

3つ目　(A, A, A, B, A)

・・のように追加します。

ここでは、図表3のように、流れがシンプルな①の幅優先探索でプログラムを作成します。

Figure 1.3 リストperm_listとtempの考え方
Figure 1.3 リストperm_listとtempの考え方

perm_listの中の作成途中の重複順列をelmとして順次読み込み、itemは各人がどの部屋に入るかを表します。1つのelmに対しAを追加したものとBを追加したものというように複数個のタプルをperm_listに追加します。この流れでは配列perm_listを読み込みながら、そのperm_listに重複順列を追加する処理が必要になり、永久ループに陥る恐れがあります。そこで図表3のように、perm_listの内容を1度リストtempにコピーし、perm_listをクリアしたのちtempから順次読み込み、Aを付け加えた重複順列と、Bを付け加えたタプルをperm_listに追加していきます。

重複組み合わせを生成する関数

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

Code 1.2 重複組み合わせを生成する関数

  1. def generete_unrestricted_perm(k_list, n):
  2. perm_list = [()]
  3. for _ in range(n):
  4. temp = perm_list
  5. perm_list = []
  6. for elm in temp:
  7. for item in k_list:
  8. perm_list.append(elm + (item,))
  9. return perm_list
  10. n = 5
  11. k_list= ['A', 'B']
  13. unrestricted_perm_list = generete_unrestricted_perm(k_list, n)
  14. print('generete_unrestricted_perm(2, 5) =',len(unrestricted_perm_list))
  15. if unrestricted_perm_list == itertools_product_list:
  16. print('perm_unrestricted_list == itertools_product_list') 
generete_unrestricted_perm(2, 5) = 32
perm_unrestricted_list == itertools_product_list

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

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

1回目のループ: temp = [()], perm_list = [(A ,), (B, )]

2回目のループ: temp = [(A,), (B,)], perm_list = [(A, A), (A, B), (B, A), (B, B)]

3回目のループ: temp =[(A, A), (A, B), (B, A), (B, B)], perm_list = [(A, A, A), (A, A, B), (A, B, A),・・のように推移します。

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

15. #1でitertoolsにより生成したリストと比較します。

このことにより、perm_listが長さnの重複順列のリストとして返します。最終的にproduct関数の結果と一致します。作成の過程のリストをtempで仮置きして、perm_listと置き換えながら重複順列を生成するので、今一つあか抜けない感覚は拭えませんが、これ以上のプログラムを作るには意外と難しいものです。

ictsr4 All Rights Reserved.