C++で整数をそれより小さい数の和に分解する方法（分割数）を求めるプログラム

このプログラムでは、ある整数 n が「それより小さい数の総和」として表現できる方法の数、いわゆる分割数（パーティション数）を数えます。例えば n = 7 の場合、「7」「6+1」「5+2」「5+1+1」「4+3」…のように合計14通りの分割が存在します。

処理の流れはシンプルです。まず入力として数 n を受け取り、配列の先頭要素を n とします。その後、末尾の要素から順に 1 ずつ取り除いて新しい分割を生成し、分割がひとつ作られるたびにカウンターを増やしていきます。すべての要素が 1 になった時点で処理を終了し、カウントした総数を返します。

アルゴリズム

partitionCount(n)

入力：整数 n

出力：分割の総数

Begin
    サイズ n の配列 p を用意する
    k := 0
    count := -1
    配列 p の最初の要素として n を格納する
    以下の手順を繰り返す
        count を 1 増やす
        rem := 0
        k >= 0 かつ p[k] = 1 の間、繰り返す
            rem := rem + p[k]
            k を 1 減らす
        繰り返しここまで
        もし k < 0 ならば
            count を返して終了
        p[k] := p[k] - 1
        rem := rem + 1
        rem >= p[k] の間、繰り返す
            p[k+1] := p[k]
            rem := rem - p[k]
            k を 1 増やす
        繰り返しここまで
        p[k+1] := rem
        k を 1 増やす
    繰り返しここまで
End

サンプルコード

#include<iostream>
using namespace std;
int partitionCount(int n){ // すべての可能な分割を数える関数
    int p[n], k = 0, count = -1;
    p[k] = n; // 配列の最初の要素として n を追加
    while(true) { // すべての要素が 1 になるまで繰り返す
        count++;
        int rem = 0;
        while (k >= 0 && p[k] == 1){ // p[k] > 1 となる正しいインデックスへポインタを移動
            rem += p[k];
            k--;
        }
        if (k < 0) // k < 0 なら、すべての要素が 1 まで分解されたことを意味する
            return count;
            // そうでなければ値を 1 減らし、rem を増やす
            p[k]--;
            rem++;
        while (rem > p[k]) { // 残りの値がインデックス k の値より大きくなるまで繰り返す
            p[k+1] = p[k];
            rem -= p[k]; // 残り値 rem を減らす
            k++;
        }
        p[k+1] = rem; // 残った値を k の次のインデックスに代入
        k++;
    }
}
main() {
    int n, c;
    cout<<"分割数を求める整数を入力してください: ";
    cin>>n;
    if (n <= 0) { // n は 1 以上である必要がある
        cout<<"無効な n の値です";
        exit(1);
    }
    c = partitionCount(n);
    cout<<"分割の総数: "<<c;
}

実行結果

分割数を求める整数を入力してください: 7
分割の総数: 14

補足：n = 7 の場合の14通りの分割

参考までに、n = 7 のときに数えられる14通りの分割は以下の通りです。

7 ／ 6+1 ／ 5+2 ／ 5+1+1 ／ 4+3 ／ 4+2+1 ／ 4+1+1+1 ／ 3+3+1 ／ 3+2+2 ／ 3+2+1+1 ／ 3+1+1+1+1 ／ 2+2+2+1 ／ 2+2+1+1+1 ／ 2+1+1+1+1+1 ／ 1+1+1+1+1+1+1

※厳密には「7」自身も1つの分割として含まれるため、上記は15項目ありますが、アルゴリズム上は初期状態の n 自体を除いた生成回数をカウントする設計になっています。この点は実装の仕様として理解しておくとよいでしょう。