分割数　制約なし　N,Kともラベルなし

不定方程式を使い分割数を生成する

分割数の考え方と生成方法

分割数の考え方

これまで、写像の考え方を使い集合N、Kともに、またはいずれかに区別があるものを扱ってきました。最後に、集合N、Kともに区別のつかない写像を扱います。単純化と思いきや、実は非常に複雑で奥深いものがあります。それではさっそく次の問題を考えます。

Example 4.1

整数6をいくつかの正の整数の和であらわしてください。ただし、1+2+3、2+3+1などは区別せず、１つの組み合わせと考えます。

答えは、次の11通りになります。

(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)、 (2+ 2+ 2)

(5+ 1)、(4+ 2)、(3+ 3)

(6)

このような1つ１つの整数の和の組合せ、例えば3+ 2+ 1を分割 (partition)、3,2や1のように分割を構成する個々の正の整数を和因子(part)、3+2+1は3つの和因子の組合せになり、この3を和因子数（number of parts）と呼びます。また、正の整数nに対する分割の個数は分割数(partition number)と呼び、p(n)であらわします。例えばp(6)=11 (partition number of 6 is 11)と読みます。分割は3+ 2+ 1のように大きい数の大きいものから小さい数の順（降順）に並べ、(3, 2, 1) と表記することにします。たかだか6のような小さな整数でも、思いつくままに書き出していたのでは正確に数え上げるのは容易ではありません。そこでFigure 4.1のように、写像を使って整理します。

6の分割の場合、和因子数が1から6までの範囲になり、分割を見ていると全射・単射の制限がない任意の写像である弱組成において、集合Kについて区別のつかない写像に再構築したものであることに気づきます。

任意写像の弱組成を生成し、単純減少写像を抽出

generate_weak_compositionでn=6、k=6の弱組成を生成し、ここからfilter_increasing_map関数を使い、広義の単純減少写像を抽出します。組み合わせの生成で使用したfilter_increasing_map関数を使うとリストから昇順のものを抜き出すことができますが、狭義単調増加（strictly increasing)にしか対応できていません。一方、

分割数は降順でなおかつ同じ数が並んでもよい（広義単調増加：weakly increasing）という条件なので、これまでのプログラムでは条件に対応できません。そこでfilter_increasing_map関数に引数を追加してstrict=Trueをデフォルトにしながらも、Falseとすると同じものがあっても抜き出すように改良します。またreverse=Trueとすることで、降順の要素を抜き出すことができるようにします。もちろん、この関数は昇順で使うことの方が多いので、reverseを指定しなければFalseとなり昇順の要素を抜き出すようにします。

Code 4.1　n=k=6の弱組成を生成する

n = 6
weak_composition_list = generate_weak_composition(n, n)
decreasing_composition_list = filter_increasing_map(
weak_composition_list,
strict = False,
reverse = True
)
decreasing_composition_list

[(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)]

3.　任意写像のためn=k=6になるので、n=6として同じ引数を指定します。

分割数は11で正しく計算できていますが、k=6の弱組成であることから0が入っています。そこで0を削除する処理をします。

増加写像の考え方を使いラベルを外す

decreasing_composition_listは単純減少写像なので、削除する必要がある0はシーケンスの右側に集まっています。このため、読み込んだシーケンスを末尾から順次読み込み、0であればその0を削除する処理を繰り返します。

Code 4.2　増加関数または減少関数の配列を抜き出す

partition_list_from_composition = []
for seq in decreasing_composition_list:
while seq[-1] == 0:
seq = seq[:-1]
partition_list_from_composition.append(seq)
print(
f'count of partition from composition ({n}) : '
f'{len(partition_list_from_composition)}'
)
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を最後の要素を順次参照します。4行目で0の要素を削除しますが、0でなくなるまでこの処理を繰り返します。

4.　seqの最後の要素を削除します。seqはタプルなのでインデックスが0から最後の1つ前までをスライスし、新たに同じ名前のseqというタプルを作成します。

SymPyライブラリによる分割数の表示

PythonのSymPyライブラリには、分割数の計算や分割の生成をする関数が用意されています。これらを使い、これまでの計算結果を確認します。

分割数を計算するSymPyライブラリのpartition関数

分割数はSymPyライブラリのpartition関数を使用することにより計算することができます。

Code 4.3　SymPyライブラリで分割数の計算をする

from sympy import partition
sym_partition_cnt = partition(n)
print(type(sym_partition_cnt))
print(f'partition={int(sym_partition_cnt):>3}')


partition= 11

2.　partition関数の戻り値はsympy.core.numbers.Integerクラスという特別な形式の整数の型になります。このため、3．で出力する場合にはint関数を適用します。

SymPyライブラリのpartition関数で、nに応じた分割数の数を計算することができます。N=6の場合11個ということで、計算結果と一致することがわかります。

分割を生成するpartitions関数

SymPyライブラリのpartitions関数

SymPyライブラリのsympy.utilities.iterablesモジュールで提供されるpartitions関数を使用することにより分割を生成することができます。

Code 4.4　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関数の戻り値はジェネレータ形式になるのでsym_partitions_genという変数に結果を代入します。

4.　生成した結果を確認し、次の処理で比較をするために利用するのでリスト形式に変換します。

分割数は11となり、計算結果も正しいように見えますが辞書形式となっています。自作関数と比較するため、辞書形式をタプルに変換します。

辞書形式をリストに変換する関数

分割を生成することができましたが、出力結果は辞書形式となっており、他のプログラムによる出力結果を比較することができないので、タプルに変換します。辞書からタプルやリストのようなシーケンスにへの変換は今後も使用することが想定されるので、dict_convert_to_seq関数とします。配列converted_listに辞書形式の分割をリストに変換して挿入します。

このプログラムは、Pythonの辞書（dict型）を受け取り、各キーを「その値の数だけ」リスト内に繰り返して展開した新しいリストを生成する関数です。たとえば、{"a": 2, "b": 3} という辞書を渡すと、["a", "a", "b", "b", "b"] というリストが返されます。この関数は、キーとその出現回数の関係を持つ辞書データを、単純なリスト構造に変換したい場合に有用です。

Code 4.5　辞書形式をリストに変換する関数で分割のリストを作成

def dict_convert_to_seq(input_dict, return_list=False):
converted_list = []
for key, value in input_dict.items():
converted_list.extend([key] * value)
return converted_list if return_list else tuple(converted_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 はその数を表す整数です。

4.　キーを「値の数」だけ繰り返すリスト [key] * value を生成し、converted_list の末尾に追加しています。

5.　引数がreturn_list=Falseの場合がデフォルトでタプルを返します。

SymPyライブラリordered_partitions関数

SymPyライブラリにはpartitionsのほか、分割を生成する関数としてsympy.utilities.iterablesモジュールで提供されるordered_partitions関数があります。ordered_partitions関数ではリストで分割を生成されますが、個々の分割の並びが昇順になります。そこで、分割の定義から降順になるための工夫をします。

Code 4.6　ordered_partitions関数で分割を生成する

from sympy.utilities.iterables import ordered_partitions
sym_ordered_partitions_list=list(ordered_partitions(n, sort = True))
sym_ordered_partitions_list

[[1, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 2],
 [1, 1, 1, 3],
 [1, 1, 2, 2],
 [1, 1, 4],
 [1, 2, 3],
 [1, 5],
 [2, 2, 2],
 [2, 4],
 [3, 3],
 [6]]

3.　ordered_partitions関数のsortパラメーターをTrueにすると分割が辞書のように降順で生成されます。Sort=Falseとしても結果は変わりませんが、プログラムの流れで生成された順番で出力されるといわれているので、Trueとしておいた方が無難です。

シーケンスの並びが単純増加写像になってはいるものの、分割を生成することができました。しかし

Code 4.7　ordered_partitions関数で分割を生成する

reversed_list = []
for p in ordered_partitions(n, sort = True):
reversed_list.append(p[::-1])
reversed_sym_ordered_partitions_list = convert_to_tuple(reversed_list)
reversed_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,)]

4.　ordered_partitions関数では、昇順で分割が生成されるので降順に変換します。リストに対して[::-1]とスライスすることにより並びを逆転させることができます。

コンボジッションから生成した分割とSymPyライブラリの関数の結果を比較

Code 4.8　不定方程式から生成した分割とSymPyの2つの関数で生成した分割を比較

if (
sorted(partition_list_from_composition)
== sorted(sym_partitions_list)
== sorted(reversed_sym_ordered_partitions_list)
):
print('list from composition == SymPy_partitions ==SymPy_ ')

list from composition == SymPy_partitions ==SymPy_

1.　連鎖比較（chained comparison）を使うことにより、3つのオブジェクトを比較することができます。

任意写像のコンポジッションを降順のものだけを抜き出すことによって生成した分割はSymPyライブラリのordered_partitions関数およびpartitions関数の結果が等しくなることがわかりました。ただし、ordered_partitions関数とpartitions関数は今後の展開において、少し異なる結果をもたらすようになります。

Code 4.9　増加関数または減少関数の配列を抜き出す

def generate_partition(n):
composition_list = [()]
for i in range(n):
next_composition = []
for seq in composition_list:
remaining = n - sum(seq)
if remaining == 0:
next_composition.append(seq)
else:
if i == 0:
start = n
else:
start = min(seq[-1],remaining)
for num in range(start,0 , -1):
next_composition.append(seq + (num,))
composition_list = next_composition
return composition_list
generate_partition(6)

[(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)]

Code 4.10　増加関数または減少関数の配列を抜き出す

if partition_list==sym_partitions_list:
print('partition_list == SymPy_partitions ')

partition_list == SymPy_partitions

n=6、和因子数が3の分割は(3,2,1),(4,1,1),(2,2,2)の3つであることが分かりました。

分割数 制約なし N,Kともラベルなし