分割数を写像から考える

漸化式を応用して分割数を計算する

分割数の計算

漸化式を使った分割数を計算する関数をまとめます。この関数では、引数にnのみを指定した場合は分割数、(n,k)を指定した場合は補助関数、aster=Trueとしたときはk個以下の合計を計算することとします。

漸化式を使って分割数の個数を計算する

  1. def partition(n, k=None, aster=False):
  2. if aster:
  3. n += k
  4. elif k is None:
  5. k = n
  6. n = 2 * n
  8. if n < k:
  9. return 0
  10. if k == 1 or n == k:
  11. return 1
  12. return partition(n-1, k-1) + partition(n-k, k)
  14. print(partition(6,3))
  15. print(partition(6,3,aster=True),partition(6,1)+partition(6,2)+partition(6,3))
  16. print(partition(6),partition(6,6,aster=True))
3
7 7
11 11

2.　asterがTrueの場合、nにkを加え、n+kとします。なお、if aser はif aster=Trueと同じことです。

3.　kに値が指定されない場合は、分割数と考え、k=n,n=2*nとします。このように引数に何も指定されない場合に、具体的な数値ではなく、計算結果を初期値として大雄するとときにはk=Noneというように指定します。

4.　ある値がNoneかを判断するときはis演算子を使います。

==値の等価性を比較するのに対し、isは同じオブジェクトかどうかを判断します。

このような、すっきりとした関数で分割数を計算することができるのは驚きです。

漸化式を使った分割の生成

p(n,k)関数の応用

p(n,k)を使い、漸化式を使って分割を生成する関数を作成ます。pn_list_func関数とpn_aster_list_funcは再掲です。新規に作るのはpartition_generate_func_p関数だけです。

分割数の作成

  1. def pn_list_func(n, k):
  2. if n < k:
  3. return []
  4. if k==1:
  5. return [[n]]
  6. array = []
  7. for elm in pn_list_func(n-1, k-1):
  8. array.append(elm+[1])
  9. for elm in pn_list_func(n-k, k):
  10. array.append([item+1 for item in elm])
  12. return array
  14. def pn_aster_list_func(n, k):
  15. array = []
  16. for elm in pn_list_func(n+k, k):
  17. new_elm = []
  18. for item in elm:
  19. if item > 1:
  20. new_elm.append(item-1)
  21. array.append(new_elm)
  22. return array
  24. def partition_generate_func_p(n):
  25. return pn_aster_list_func(n, n)
  27. partition_generate_func_p(6)
[[6],
 [5, 1],
 [4, 2],
 [3, 3],
 [4, 1, 1],
 [3, 2, 1],
 [2, 2, 2],
 [3, 1, 1, 1],
 [2, 2, 1, 1],
 [2, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1]]

24.pn_aster_list_func関数に、引数n=n,k=nにより呼び出すだけです。

こうしてみると、いずれの方法でも分割を生成することができますが、この目的ではqnの方がより簡単に処理できるように思われます。

qnを使って整数分割を生成する

以前作成したqn_list_func関数を使って、整数分割を生成します。

qnから分割数を作成

  1. def qn_list_func(n, k):
  2. if n < k:
  3. return []
  4. if k==1:
  5. return [[1] * n]
  6. array = []
  7. for elm in qn_list_func(n-1, k-1):
  8. array.append([elm[0] + 1] + elm[1:])
  9. for elm in qn_list_func(n-k, k):
  10. array.append([k] + elm)
  11. return array
  13. def qn_aster_list_func(n, k):
  14. array = []
  15. for elm in qn_list_func(n+k, k):
  16. array.append(elm[1:])
  17. return array
  19. def partition_generate_func_q(n):
  20. return qn_aster_list_func(n, n)
  22. partition_generate_func_q(6)
[[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]]

24.pn_aster_list_func関数に、引数n=n,k=nにより呼び出すだけです。

partition_generate_func_q関数と同じ結果ですが、出力される順番が逆になります。このように分割数には興味が尽きません。

ictsr4 All Rights Reserved.