皆さん、こんにちは。管理人です。今回は、与えられた負でない整数 \(n\) の分割すべてを列挙するプログラムを Python で作りました、という内容です。
整数の分割とは
負でない整数 \(n\) が与えられたとき、\(n\) を正の整数の和で表すことを考えます。例えば \(4\) は
- \(4\)
- \(3 + 1\)
- \(2 + 2\)
- \(2 + 1 + 1\)
- \(1 + 1 + 1 + 1\)
というふうに表すことができますが、これらを \(4\) の分割と呼びます。ただし、足し算の順番が違うだけの式は同一視するものとします。例えば、次の \(3\) つの式はすべて同一のものとみなします。
- \(2 + 1 + 1\)
- \(1 + 2 + 1\)
- \(1 + 1 + 2\)
ちなみに、足されているひとつひとつの数を和因子といいます。例えば、\(10\) の分割 \(5 + 2 + 2 + 1\) を考えたとき、その和因子は \(5\) と \(2\) と \(1\) です。通常、和因子は左に大きいものがくるように並べます。
今回作成したのは、負でない整数 \(n\) を標準入力から入力したときに \(n\) の分割すべてを列挙する Python のプログラムです。ただし、分割はリストとして表現するようにしました。
ソースコード
プログラムのソースコードは次のとおりです。
n = int(input('負でない整数を入力してください: '))
count = 0
def partitions(remain, max_summand, summands):
global count
if remain == 0:
count = count + 1
print(count, ':', summands)
else:
i = max_summand
while i > 0:
if remain >= i:
summands.append(i)
partitions(remain - i, i, summands)
summands.pop()
i = i - 1
partitions(n, n, [])
実行結果
上に挙げたプログラムの実行結果の例を次に二つ挙げます。
負でない整数を入力してください: 6
1 : [6]
2 : [5, 1]
3 : [4, 2]
4 : [4, 1, 1]
5 : [3, 3]
6 : [3, 2, 1]
7 : [3, 1, 1, 1]
8 : [2, 2, 2]
9 : [2, 2, 1, 1]
10 : [2, 1, 1, 1, 1]
11 : [1, 1, 1, 1, 1, 1]
負でない整数を入力してください: 8
1 : [8]
2 : [7, 1]
3 : [6, 2]
4 : [6, 1, 1]
5 : [5, 3]
6 : [5, 2, 1]
7 : [5, 1, 1, 1]
8 : [4, 4]
9 : [4, 3, 1]
10 : [4, 2, 2]
11 : [4, 2, 1, 1]
12 : [4, 1, 1, 1, 1]
13 : [3, 3, 2]
14 : [3, 3, 1, 1]
15 : [3, 2, 2, 1]
16 : [3, 2, 1, 1, 1]
17 : [3, 1, 1, 1, 1, 1]
18 : [2, 2, 2, 2]
19 : [2, 2, 2, 1, 1]
20 : [2, 2, 1, 1, 1, 1]
21 : [2, 1, 1, 1, 1, 1, 1]
22 : [1, 1, 1, 1, 1, 1, 1, 1]
コメント