C++で整数の分割（パーティション）をすべて生成するプログラムの実装方法

本記事では、与えられた正の整数 n を正の整数の和として表現する、すべての一意な分割（パーティション）を生成する C++ プログラムを紹介します。例えば 4 という整数は、「4」「3 + 1」「2 + 2」「2 + 1 + 1」「1 + 1 + 1 + 1」のように、複数の組み合わせで表すことができます。このプログラムは、そのような組み合わせを重複なくすべて出力します。

アルゴリズムの考え方

基本的な戦略は「最初に最大の要素だけからなる分割から始め、規則的に次の分割を生成していく」というものです。擬似コードで示すと以下のようになります。

開始
　　関数 displayAllUniqueParts(int m):
　　分割を格納するための配列 p[m] を宣言する。
　　分割内の最後の要素のインデックス k を 0 に設定する。
　　最初の分割を「数そのもの」で初期化する：p[k] = m

　　現在の分割を表示し、続けて次の分割を生成する while ループを作る。
　　現在の分割がすべて 1 になった時点でループを終了する。

　　displayArray(p, k + 1) により現在の分割を表示する。

　　次の分割を生成する手順：
　　変数 val を 0 で初期化する。
　　p[] の中で最も右側にある「1 以外の値」を探し、
　　あとどれだけの値を振り分けられるかを val に記録する。

　　もし k < 0 ならば、
　　　　すべての値が 1 であるため、これ以上の分割は存在しない。

　　上で見つけた p[k] を 1 減らし、val を調整する。

　　もし val が p[k] より大きい場合、
　　　　ソート順序が崩れるため、val をサイズ p[k] の値に
　　　　分割し、p[k] の後ろの各位置へコピーする。
　　　　残った val を次の位置にコピーし、位置を進める。
終了

サンプルコード

以下が実際の C++ 実装です。関数 printAllUniqueParts が分割の生成を担当し、補助関数 printArr が配列の内容を出力します。

#include<iostream>
using namespace std;

void printArr(int p[], int m) {
    for (int i = 0; i < m; i++)
        cout << p[i] << " ";
    cout << endl;
}

void printAllUniqueParts(int m) {
    int p[m];
    int k = 0;
    p[k] = m;

    while (true) {
        // 現在の分割を表示
        printArr(p, k + 1);

        // 次の分割を生成
        int rem_val = 0;
        while (k >= 0 && p[k] == 1) {
            rem_val += p[k];
            k--;
        }

        if (k < 0)
            return;

        p[k]--;
        rem_val++;

        while (rem_val > p[k]) {
            p[k + 1] = p[k];
            rem_val = rem_val - p[k];
            k++;
        }

        p[k + 1] = rem_val;
        k++;
    }
}

int main() {
    cout << "All Unique Partitions of 3\n";
    printAllUniqueParts(3);

    cout << "\nAll Unique Partitions of 4\n";
    printAllUniqueParts(4);

    cout << "\nAll Unique Partitions of 5\n";
    printAllUniqueParts(5);

    return 0;
}

実行結果

このプログラムをコンパイルして実行すると、以下のような出力が得られます。各整数について、降順に並んだ一意な分割がすべて列挙されていることが確認できます。

All Unique Partitions of 3
3
2 1
1 1 1

All Unique Partitions of 4
4
3 1
2 2
2 1 1
1 1 1 1

All Unique Partitions of 5
5
4 1
3 2
3 1 1
2 2 1
2 1 1 1
1 1 1 1 1

処理のポイント

• 初期化： 最初の分割は常に「その数自身」（例：5）から始まります。
• 右端の探索： 配列の右端から「1 以外の値」を探し、そこを基準に次の分割を組み立てます。
• 余りの再分配： 探索中に集めた 1 の合計（rem_val）を、ソート順序（非増加順）を保ちながら右側の要素に振り分けていきます。
• 終了条件： 分割がすべて 1 になったとき（k < 0 となったとき）、すべてのパターンを出力し終えたことになります。

この手法はバックトラック的な発想を用いた効率的な実装であり、整数分割の全列挙が必要な場面（組合せ論の問題や動的計画法の学習など）で役立ちます。