与えられた整数のすべての一意な分割（パーティション）を生成するC++プログラム

本記事では、正の整数 n を入力として受け取り、n を正の整数の和として表すすべての一意な分割（パーティション）を生成するC++プログラムを紹介します。

「分割」とは、ある整数を複数の正の整数の組み合わせに分解する方法のことです。たとえば 4 であれば、「4」「3+1」「2+2」「2+1+1」「1+1+1+1」のように、要素の順序が異なるだけで構成が同じものは同一の分割として扱われます。このプログラムでは、重複のない形ですべての分割パターンを列挙します。

アルゴリズム

関数 displayAllUniqueParts(int m) の処理手順は以下のとおりです。

Begin
function displayAllUniqueParts(int m):
    1) 分割の中で最後の要素となるインデックス k を 0 に設定する
    2) 最初の分割として、数そのものを格納する（p[k] = m）
    3) 現在の分割を表示した後、次の分割を生成する while ループを作成する。
       現在の分割がすべて 1 になった時点でループを終了する
    4) 現在の分割を displayArray(p, k + 1) で表示する
    5) 次の分割を以下の手順で生成する：
    6) val を 0 で初期化する
       p[] の中から最も右側にある「1 以外の値」を探索し、
       あわせて val を更新して、いくつの値を収容できるかを把握する
       k < 0 となった場合は、すべての値が 1 であることを意味し、
       これ以上の分割は存在しない
       見つかった p[k] を 1 減らし、それに応じて val を調整する
    7) val が大きすぎる場合はソート済みの並び順が崩れるため、
       val を p[k] 以下の大きさの複数の値に分割し、
       p[k] の後ろの各位置へコピーする
       残りの val を次の位置にコピーし、位置を 1 つ進める
End

サンプルコード

#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;
        p[k]--;
        val++;
        while (val > p[k]) // val が大きすぎる場合
        {
            p[k + 1] = p[k];
            val = val - p[k];
            k++;
        }
        p[k + 1] = val;
        k++;
    }
}
int main()
{
    cout << "Display All Unique Partitions of 3\n";
    displayAllUniqueParts(3);
    cout << "\nDisplay All Unique Partitions of 4\n";
    displayAllUniqueParts(4);
    cout << "\nDisplay All Unique Partitions of 5\n";
    displayAllUniqueParts(5);
    return 0;
}

実行結果

Display All Unique Partitions of 3
3
2 1
1 1 1
Display All Unique Partitions of 4
4
3 1
2 2
2 1 1
1 1 1 1
Display 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

プログラムのポイント

このプログラムでは、配列 p を使って現在の分割を降順に保持しながら、右端の要素を少しずつ操作することで「次の分割」を系統的に生成しています。右端から連続する 1 を取り除いて合計値 val に加算し、直前の要素を 1 減らすことで余りを生み出し、その余りを降順の制約を保ちながら後ろの位置に再配置するのが核心的なロジックです。

すべての要素が 1 になった時点（k が負になる時点）で全パターンの列挙が完了したことになり、処理を終了します。この手法により、n=4 の場合は「4 → 3 1 → 2 2 → 2 1 1 → 1 1 1 1」というように、漏れや重複なく一意な分割を順番に出力できます。