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

本記事では、特定のケースにおける整数分割（Integer Partition）を実行するC++プログラムを紹介します。整数分割とは、ある正の整数 n を、正の整数の和として表現するすべての一意な組み合わせを求める問題です。

例えば n = 7 の場合、「7」「6+1」「5+2」「5+1+1」…といった具合に、順序の違いだけの重複を除いた形ですべての分割パターンを出力します。

アルゴリズムの流れ

このプログラムは、現在の分割を表示しながら次の分割を順次生成していく手法を採用しています。大まかな手順は以下の通りです。

1. 分割配列 p[] の末尾インデックス k を 0 に初期化します。
2. 最初の分割として、数値そのものを設定します（p[k] = m）。
3. 「現在の分割を表示 → 次の分割を生成」を繰り返す while ループを作成します。ループは、現在の分割がすべて 1 になった時点で終了します。
4. displayArray(p, k + 1) を呼び出して、現在の分割を表示します。
5. 次の分割を生成します。まず val を 0 で初期化し、配列 p[] の中で最も右側にある「1 以外の値」を探します。同時に val を更新することで、あとどれだけの値を再配置できるかを把握します。
6. k < 0 となった場合は、すべての要素が 1 であることを意味するため、これ以上の分割は存在せず処理を終了します。それ以外の場合は、見つかった p[k] を減らし、val を調整します。
7. val が p[k] より大きい場合は、ソート済みの順序が崩れるため、val を p[k] 以下の複数の値に分割し、p[k] の後ろの各位置へコピーしていきます。残った val は次の位置にコピーし、位置を進めます。

C++サンプルコード

#include<iostream>
using namespace std;

void displayArray(int p[], int m) { // 配列を表示する関数
    for (int i = 0; i < m; i++)
        cout << p[i] << " ";
    cout << endl;
}

void displayAllUniqueParts(int m) {
    int p[m];
    int k = 0;
    p[k] = m; // 最初の分割は数値そのもの

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

        int val = 0; // val を初期化
        while (k >= 0 && p[k] == 1) {
            val += p[k]; // val を更新
            k--;
        }

        if (k < 0)
            return; // すべて1なら終了

        p[k]--;
        val++;

        // val が大きすぎる場合は分割して配置
        while (val > p[k]) {
            p[k + 1] = p[k];
            val = val - p[k];
            k++;
        }
        p[k + 1] = val;
        k++;
    }
}

int main() {
    cout << "Display All Unique Partitions of integer:7\n";
    displayAllUniqueParts(7);
    return 0;
}

実行結果

n = 7 を指定して実行すると、以下のように15通りのすべての一意な分割が出力されます。

Display All Unique Partitions of integer:7
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

まとめ

このアルゴリズムは、右端から「1 以外の値」を見つけて減算し、余った値を適切なサイズに分割して再配置することで、辞書順に近い形で効率よくすべての分割を列挙できます。計算量は分割数に比例するため、動的計画法による分割数のカウントと組み合わせると、より高度な応用にも発展させられます。