重複順列

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

全射でも単射でもない制約なしの重複順列

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

問題1

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

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

重複順列の考え方

写像からみた重複順列

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

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

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

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

上記のことから、重複順列は制約なし（unrestricted）の写像ということができます。

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

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

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

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

重複順列の個数

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

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

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

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

product関数で重複順列を生成するときは、集合の要素とnの個数をrepeat=nの形式で引数を渡します。

戻り値として0,1,・・4が選んだ部屋がAかBかを表すイテレータが生成されます。また、リストはpprint関数を使うと見やすく表示することができるので、あらかじめpprintをインポートしておきます。

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

  1. import itertools
  2. import pprint
  3. k_list = ['A', 'B']
  4. itertools_product_list = list(itertools.product(k_list, repeat = 5))
  5. print('itertools product(2, 5) =',len(itertools_product_list))
  6. pprint.pprint(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.　イテレータをリストとして扱うときには、list関数を使いリスト型に変換する必要があります。

6.　生成した重複順列は、pprint関数で出力すると行ごとに表示され見易くなります。

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

重複順列を生成する関数

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

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

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

少し専門的になりますが、幅優先探索（BFS = Breadth-First Search）という方法です。

初期の定義時:  array = [(, )]

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

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

3回目のループ:  array = [(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のように、流れがシンプルな①の幅優先探索でプログラムを作成します。

リストarrayとtempの考え方
リストarrayとtempの考え方

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

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

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

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

関数名
perm_unrestricted_func
重複順列を生成する
引　数
k_list
集合Kの要素をタプルで指定
n
集合Nの要素の個数を指定
返り値
perm_unrestricted_list
重複順列を2重リスト形式で返す。
関数名
perm_unrestricted_func
重複順列を生成します。
引　数
k_list
集合Kの要素をタプルで指定
引　数
n
集合Nの要素の個数を指定
返り値
perm_unrestricted_list
重複順列を2重リスト形式で返します。
  1. def perm_unrestricted_func(k_list, n):
  2. array = [()]
  3. for _ in range(n):
  4. temp = array
  5. array = []
  6. for elm in temp:
  7. for item in k_list:
  8. array.append(elm + (item,))
  9. return array
  10. n = 5
  11. k_list= ['A', 'B']
  13. perm_unrestricted_list = perm_unrestricted_func(k_list, n)
  14. print('perm_unrestricted_func(2, 5) =',len(perm_unrestricted_list))
  15. if perm_unrestricted_list == itertools_product_list:
  16. print('perm_unrestricted_list == itertools_product_list')
perm_unrestricted_func(2, 5) = 32
perm_unrestricted_list == itertools_product_list

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

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

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

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

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

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

このことにより、arrayが長さnの重複順列のリストとして返します。最終的にproduct関数と同じ結果になります。

ictsr4 All Rights Reserved.