整数の分割を列挙するプログラムを Python で作りました

皆さん、こんにちは。管理人です。今回は、与えられた負でない整数 \(n\) の分割すべてを列挙するプログラムを Python で作りました、という内容です。

Contents

整数の分割とは
ソースコード
実行結果

整数の分割とは

負でない整数 \(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]