JavaScriptで整数分割のすべてのパターンを求める方法

整数分割（パーティション）とは？

正の整数 n の「分割」とは、n を正の整数の和として表現する方法のことです。ただし、足し合わせる項の順序が異なるだけで実質的に同じになるものは、同一の分割とみなされます。

例えば、4 は以下の5通りの異なる方法で分割できます。

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

今回の課題は、正の整数を唯一の引数として受け取るJavaScript関数を作成することです。この関数は、その整数に対して可能なすべての分割の総数を見つけ出し、返却する必要があります。

アプローチ：動的計画法（DP）

分割の総数を効率よく求めるには、動的計画法（Dynamic Programming）が有効です。2次元のDPテーブルを作成し、各行を「使用できる最大の部分の値」、各列を「対象となる合計値」として扱います。

漸化式のポイントは次のとおりです。

• i > j の場合： i より大きい部分は使えないため、arr[i][j] = arr[i - 1][j] となります。
• それ以外の場合： 「i を含まない分割の数」と「i を少なくとも1つ含む分割の数」の合計を計算します。つまり arr[i][j] = arr[i - 1][j] + arr[i][j - i] です。

最終的な答えは arr[num][num]、つまり num までの値を自由に使って num を作る場合の分割数となります。

コード例

以下がその実装コードです。

const findPartitions = (num = 1) => {
    const arr = Array(num + 1).fill(null).map(() => {
        return Array(num + 1).fill(null);
    });
    for (let j = 1; j <= num; j += 1) {
        arr[0][j] = 0;
    }
    for (let i = 0; i <= num; i += 1) {
        arr[i][0] = 1;
    }
    for (let i = 1; i <= num; i += 1) {
        for (let j = 1; j <= num; j += 1) {
            if (i > j) {
                arr[i][j] = arr[i - 1][j];
            }
            else {
                const exclusive = arr[i - 1][j];
                const inclusive = arr[i][j - i];
                arr[i][j] = exclusive + inclusive;
            }
        }
    }
    return arr[num][num];
};
console.log(findPartitions(4));

実行結果

コンソールには以下の出力が表示されます。

5

これは冒頭で示したとおり、4 を分割する方法がちょうど5通り存在することを意味しています。この手法の計算量は O(n²) であり、単純な全列挙よりもはるかに高速に分割数を算出できます。