分割数
強組成を使い分割数を生成する
分割数の考え方
分割数について理解するため次の問題を考えます。
Example 4.1
整数6を3個の正の整数の和であらわしてください。ただし、3+2+1、1+2+3、2+3+1などは区別せず、１つの組合せと考えます。
整数6を１個から6個までの正の整数の和であらわしてください。ただし、2+2+1+1、1+1+2+2などは区別せず、１つの組合せと考えます。
(1)の答えは
2+2+2
3+2+1
4+1+1
の3通りになります。
(2)はこれに
1 + 1+ 1+ 1+ 1+ 1
2 + 1+ 1+ 1+ 1
3 + 1+ 1+ 1
2 + 2+ 1+ 1
5 + 1
4 + 2
3 + 3
6
の8通りを加え、計11通りになります。
このような1つ１つの整数の和の組合せ、例えば2+2+1+1を分割 (partition)、2や1のように分割を構成する個々の正の整数を和因子(part)と呼びます。また、2+2+1+1は4つの和因子の組合せになり、この4を和因子数（number of parts）、正の整数nに対する分割の個数は分割数(partition number)と呼び、p(n)であらわします。例えばp(6)=11 (partition number of 6 is 11)と読みます。分割は3+2+1のように降順に並べ、(3, 2,1) と表記することにします。たかだか6のような小さな整数でも、思いつくままに書き出していたのでは正確に数え上げるのは容易ではありません。そこで手始めに(1)のように和因子数が3の分割について検討します。
和因子数がkの分割は全射の写像
強組成から全射の分割を生成する
(1)の問題は写像にすると、集合N、集合Kともに区別のつかない全射の対応になります。つまり、集合Kだけ相異なる全射の対応である強組成（strong composition）$x_1+x_2+x_3 \lt6\quad(x_i\geqq1)$の解に対して、$x_1\geqq x_2 \geqq x_3$の条件で抽出したものになります。
generate_strict_composition 関数でn=6,k=3での強組成を生成し、その結果をfilter_increasing_map関数で降順のものを抽出します。
Code 4.1 k=3の強組成から単純減少写像を抽出
- n = 6; k = 3
- strict_composition_list = generate_strict_composition(k, n)
- decreasing_strict_composition_list = filter_increasing_map(
- strict_composition_list,
- strict = False,
- increase = False
- )
- print(f'strict_composition : {len(strict_composition_list)}')
- print(f'decreasing_strict_composition : {len(decreasing_strict_composition_list)}' )
- decreasing_strict_composition_list
[(2, 2, 2), (3, 2, 1), (4, 1, 1)]
2. generate_strict_compositionでは、組合せの関係からkとnが逆転します。
5. filter_increasing_map関数でstrict = Falseとすることで同じ数が続くことも許した降順にすることができます。
分割は(2, 2, 2), (3, 2, 1), (4, 1, 1)の3通りとなり、組合せも前節の答えと結果が一致しました。
SymPyライブラリの分割に関する関数
分割数を計算する関数
分割数はSymPyライブラリのsympy.functions.combinatorial.numbersモジュールが提供するnT関数を使用することにより計算することができます。
Code 4.2 SymPyライブラリのnT関数により分割数を計算
- from sympy.functions.combinatorial.numbers import nT
- sym_nt_count = nT(n, k)
- print(type(sym_nt_count))
- print(f'partition ={int(sym_nt_count):>3}')
partition = 3
3. nT関数の戻り値はsympy.core.numbers.Integerクラスという特別な形式の整数のフォーマットになります。
4. f-文字列を使ったフォーマット表記は、上記の特殊な形式は使えないのでint関数を適用します。
分割を生成するordered_partitions関数
SymPyライブラリのsympy.utilities.iterablesモジュールが提供するordered_partitions関数により生成することができます。ordered_partitionsは、各分割が昇順で表示されるので、逆順に並び替える必要があります。
Code 4.3 SymPyライブラリのordered_partitions関数で和因子3の分割を生成
- from sympy.utilities.iterables import ordered_partitions
- sym_strict_ordered_partitions_list = []
- for p in ordered_partitions(n, k, sort=True):
- print(p)
- sym_strict_ordered_partitions_list.append(tuple(p[::-1]))
- sym_strict_ordered_partitions_list
[1, 1, 4] [1, 2, 3] [2, 2, 2] [(4, 1, 1), (3, 2, 1), (2, 2, 2)]
5. オブジェクト再利用型（Mutable Buffer Pattern）と呼び、ジェネレータとは異なります。リストに格納するためにはスライスをしてコピーしておく必要があります。また、p[::-1]とすることにより、分割内の和因子を降順に並べ替えることができます。
ordered_partitionsの各要素は昇順になり、また各分割はリストで表現されます。そこで、分割を降順に並べ替え、convert_to_tuple関数で第2レベルをタプルに変換します。ここでの計算結果とdecreasing_composition_listをソートをして比較します。
組成から生成した分割とSymPyライブラリから生成した分割を比較
Code 4.4 組成から生成した分割とSymPyライブラリから生成した分割を比較
- def convert_to_tuple(sequence, output='tuple', depth=1):
- if isinstance(sequence, (list, tuple)):
- temp_list = [convert_to_tuple(item, output, depth + 1)
- for item in sequence]
- if output == 'list':
- return list(temp_list)
- else:
- if depth == 1:
- return list(temp_list)
- else:
- return tuple(temp_list)
- else:
- return sequence
- if (
- sorted(convert_to_tuple(sym_strict_ordered_partitions_list))
- == sorted(decreasing_strict_composition_list)
- ):
- print(f' sorted ordered partition equal partition '):
sorted ordered partition equal partition
3. オブジェクト再利用型（Mutable Buffer Pattern）と呼び、ジェネレータとは異なります。リストに格納するためにはスライスをしてコピーしておく必要があります。また、p[::-1]とすることにより、分割内の和因子を降順に並べ替えることができます。
分割数が3のように全射の場合の場合の数を計算し生成することができました。
任意写像
(2)の問題は写像にすると、区別のつかない集合Nから相異なる集合Kへの全射の写像である強組成に対し集合Kについて区別のつかない写像に変換したことになります。
この問題を写像で表します。解の1つにの解の1つに1+1+1+1+1+1があるので、最大和因子が６で$n=k=6$になります。また、解の１つを2+2+1+1は
これまで見てきた中で類似するものとして、
弱組成から単調減少写像を抽出して区別のつかない構造に変換
generate_weak_compositionでn=6、k=6の弱組成をリストweak_composition_listとして生成し、ここからfilter_increasing_map関数を使い、分割の条件である降順でなおかつ同じ数が並んでもよい（広義単調増加：weakly increasing）広義の単純減少写像を抽出します。
Code 4.5 n=k=6の弱組成を生成し広義の単調減少写像を抽出
- n = 6
- weak_composition_list = generate_weak_composition(n, n)
- decreasing_weak_composition_list = filter_increasing_map(
- weak_composition_list,
- strict = False,
- increase = False
- )
- print(f'weak_composition : {len(weak_composition_list)}')
- print(f'decreasing_weak_composition : {len(decreasing_weak_composition_list)}' )
- decreasing_weak_composition_list
weak_composition : 462 decreasing_weak_composition : 11 [(1, 1, 1, 1, 1, 1), (2, 1, 1, 1, 1, 0), (2, 2, 1, 1, 0, 0), (2, 2, 2, 0, 0, 0), (3, 1, 1, 1, 0, 0), (3, 2, 1, 0, 0, 0), (3, 3, 0, 0, 0, 0), (4, 1, 1, 0, 0, 0), (4, 2, 0, 0, 0, 0), (5, 1, 0, 0, 0, 0), (6, 0, 0, 0, 0, 0)]
2. 任意写像のためn=k=6になるので、n=6として同じ引数を指定します。
3. 減少関数であることからreverse=Trueとし、弱組成であることから広義の単調減少写像であるので、strict=Falseとしてfilter_increasing_map関数を呼びだします。
分割数は11で正しく計算できていますが、弱組成であることから要素に0が入っています。分割としての体をなすために0を削除する必要があります。
要素にある0を削除
decreasing_composition_listは単純減少写像なので、削除する必要がある0はシーケンスの右側に寄っています。このため、読み込んだシーケンスに対して末尾の0を削除すると処理を0の要素がなくなるまで繰り返します。
Code 4.6 弱組成から0を削除
- weak_partition_list_from_composition = []
- for seq in decreasing_weak_composition_list:
- while seq[-1] == 0:
- seq = seq[:-1]
- weak_partition_list_from_composition.append(seq)
- print(
- f'count of partition from composition ({n}) : '
- f'{len(weak_partition_list_from_composition)}'
- )
- weak_partition_list_from_composition
count of partition from composition (6) : 11 [(1, 1, 1, 1, 1, 1), (2, 1, 1, 1, 1), (2, 2, 1, 1), (2, 2, 2), (3, 1, 1, 1), (3, 2, 1), (3, 3), (4, 1, 1), (4, 2), (5, 1), (6,)]
3. 読み込んだシーケンスの最後の要素をseq[-1]が0である間は、4行目の処理を繰り返します。
4. seqの最後の要素（つまり0）の1つ手前までをスライスして、新たに同じ名前のseqというタプルを作成し代入します。リストであれば4行目はpopメソッドを使うことができますが、タプルはイミュータブルなので、スライスしたタプルの内容を、同じ名前の変数を新たに作成し代入します。
このように分割は集合N、Kともに区別のつかない全射・単射の制限のない任意写像であることがわかりました。次に、分割の場合の数を計算し、分割を生成する関数を実行し、上記の結果を検証します。
PythonのSymPyライブラリには、分割数の計算や分割の生成をする関数がいくつか用意されています。
SymPyライブラリのpartition関数により分割数を計算する
SymPyライブラリが提供するpartition関数を使用することにより、分割数を計算することができます。
Code 4.7 sympyライブラリのpartition関数により分割数を計算
- from sympy import partition
- sym_partition_cnt = partition(n)
- print(type(sym_partition_cnt))
- print(f'partition={int(sym_partition_cnt):>3}')
partition= 11
3. partition関数の戻り値はsympy.core.numbers.Integerクラスという特別な形式の整数の型になります。
4. sympy.core.numbers.Integerクラスはf-formatでは使用することができないのでint関数を使用し、整数型に変換します。
SymPyライブラリのpartition関数で、nに応じた分割数の数を計算することができます。n=6の場合、分割数は11個になり、計算結果と一致することがわかります。
SymPyライブラリordered_partitions関数により分割数を計算
SymPyライブラリにはpartitionsのほか、分割を生成する関数としてsympy.utilities.iterablesモジュールで提供されるordered_partitions関数があります。この関数も戻り値はジェネレータなのでlist関数でリストに変換します。
Code 4.8 ordered_partitions関数で分割を生成
- sym_ordered_partitions_list = []
- for p in ordered_partitions(n, sort=True):
- sym_ordered_partitions_list.append(tuple(p[::-1]))
- sym_ordered_partitions_list
[(1, 1, 1, 1, 1, 1), (2, 1, 1, 1, 1), (3, 1, 1, 1), (2, 2, 1, 1), (4, 1, 1), (3, 2, 1), (5, 1), (2, 2, 2), (4, 2), (3, 3), (6,)]
2. ordered_partitions関数のsortパラメーターをTrueにすると分割が辞書のように昇順で生成されます。今後の流れで生成された順番で出力されるといわれているので、Trueとしておいた方が無難です。
3. ordered_partitions関数では、sort=Trueとしているので単調増加写像であることは担保されているので、リストに対して[::-1]とスライスすることにより並びを逆転させることができます。単調増加写像であることが確認できない場合は降順のソートする必要があります。
4. convert_to_tuple関数はoutputを省略し、タプルに変換します。
分割を生成することができましたが、分割を表すシーケンスがリストになっていることと、シーケンスの並びが単純増加写像になってはいるのが気になります。そこで、広義の単調減少写像に変換したのち、convert_to_tuple関数を使いタプルに変換します。
分割の並び順にまちまちなところはありますが、弱組成から抽出したものの、SymPyライブラリが提供する2つの関数の出力結果を比較する準備が整いました。
SymPyライブラリには、分割を生成する関数が2つ用意されていますが、いずれも出力結果を加工する必要があります。
SymPyライブラリのpartitions関数
SymPyライブラリのsympy.utilities.iterablesモジュールで提供されるpartitions関数を使用することにより、分割を生成することができます。出力結果はジェネレータとなるので、後の処理を想定してリストに変換します。
Code 4.9 SymPyライブラリのpartitions関数による分割の生成
- from sympy.utilities.iterables import partitions
- sym_partitions_gen = partitions(n)
- print(type(sym_partitions_gen))
- sympy_partitions_dict = list(sym_partitions_gen)
- sympy_partitions_dict
[{6: 1}, {5: 1, 1: 1}, {4: 1, 2: 1}, {4: 1, 1: 2}, {3: 2}, {3: 1, 2: 1, 1: 1}, {3: 1, 1: 3}, {2: 3}, {2: 2, 1: 2}, {2: 1, 1: 4}, {1: 6}]
3. partitions関数の戻り値の形式をtype関数で調べます。ジェネレータ形式になるのでsym_partitions_genという変数に結果を代入します。
4. 生成した結果を確認し、次の処理で比較をするために利用するのでリスト形式に変換します。
分割数は11となり正しく計算できています。例えば、(2,2,1,1) は{2: 2, 1: 2}となるように、出力結果は和因子をキー、その和因子の個数をvalueとする辞書形式となっています。自作関数と比較するため、辞書形式をタプルに変換する必要が生じます。
辞書形式をリストに変換する関数
partitions 関数で生成した辞書の分割をタプルやリストのようなシーケンスにへの変換します。は今後も同様の処理が想定されるので、dict_convert_to_seqという関数をして作成します。この関数では{2: 2, 1: 2}のような辞書形式は2が2個と1が2個なので(2, 2, 1, 1)のように変換します。
また引数のoutputは、”tuple”とした場合タプルで、”list”として場合リストで返します。このテキストではシーケンスはタプルにするのが原則なので、省略した場合はtupleとします。なお、outputに’tuple’か’list’以外を指定した場合にはエラーを返すよう工夫します。
Code 4.10 辞書形式をリストに変換する関数で分割のリストを作成
- def dict_convert_to_seq(input_dict, output = 'tuple'):
- converted_list = []
- for key, value in input_dict.items():
- converted_list.extend([key] * value)
- if output == 'tuple':
- return tuple(converted_list)
- elif output == 'list':
- return converted_list
- else:
- raise ValueError("output must be either 'tuple' or 'list'")
- sym_partitions_list = []
- for partition_dict in partitions(n):
- sym_partitions_list.append(dict_convert_to_seq(partition_dict))
- sym_partitions_list
[(6,), (5, 1), (4, 2), (4, 1, 1), (3, 3), (3, 2, 1), (3, 1, 1, 1), (2, 2, 2), (2, 2, 1, 1), (2, 1, 1, 1, 1), (1, 1, 1, 1, 1, 1)]
3. 辞書内の全てのkey, value（個数）のペアを取得してループ処理を行います。ここで key は和因子、value はその個数を表す整数です。
4. keyの値をvalueの数だけ繰り返すリスト [key] * value を生成し、シーケンスを作成するconverted_list の末尾に追加しています。
5. 引数がreturn_list=Falseの場合がデフォルトでタプルを返します。
弱組成から生成した分割とSymPyライブラリの関数の結果を比較
弱組成から作成したリストとordered_partitions関数、partitions関数で作成したリストを比較して、正しく作成されているか確認します。
Code 4.12 弱組成から生成した分割とSymPyの2つの関数で生成した分割を比較
- if (
- sorted(partition_list_from_composition)
- == sorted(sym_partitions_list)
- == sorted(reversed_sym_ordered_partitions_list)
- ):
- print(
- f'list from composition'
- f' == SymPy_partitions'
- f' == SymPy_ordered_partitions'
- )
list from composition == SymPy_partitions == SymPy_ordered_partitions
1. 連鎖比較（chained comparison）を使うことにより、3つのオブジェクトを比較することができます。
任意写像の弱組成を降順のものだけを抜き出すことによって生成した分割はSymPyライブラリのordered_partitions関数およびpartitions関数の結果が等しくなることがわかりました。ただし、ordered_partitions関数とpartitions関数は出力する形式だけではなく、今後の展開において少し異なる挙動を示します。