JavaScriptで数値Nを2の累乗のチャンクに分割する方法【パーツ数・サイズ制限付き】

はじめに

本記事では、与えられた数値を特定のルールに従って分割（パーティション）するJavaScript関数の実装方法を解説します。分割の条件は次のとおりです。

• チャンク（パーツ）の総数は2の累乗でなければなりません。

• 各チャンクに含まれる要素数も2の累乗でなければなりません（サイズの上限は32。つまり 1, 2, 4, 8, 16, 32 のいずれか）。

具体例で理解する

たとえば 8 は、1つのバケットにそのまままとめることができます。

[8]

9 の場合は次のように分割できます。

[8, 1]

これは有効な分割です。どちらの数値も2の累乗であり、配列のサイズが2（これも2の累乗）であるためです。

次に 11 を試してみましょう。

[8, 2, 1]

一見すると合計は11ですが、この分割は無効です。配列のサイズが3であり、3は2の累乗ではないからです。

[4, 4, 2, 1]

こちらは有効です。要素数が4であり、4は2の累乗だからです。

コード例

この問題を解くコードは次のようになります。

function permuteCombinations(n, maximum){
   const maxPowerOf2 = 1 << maximum;
   const m = ~~(n / maxPowerOf2);
   const A = new Array(maximum + 1).fill(0);
   A[maximum] = m;
   let num = n − m * maxPowerOf2;
   let p = 0;
   let bitCount = 0;
   while (num){
      if (num & 1){
         bitCount += 1;
         A[p] = 1;
      }
      num >>= 1;
      p += 1;
   }
   const min = m + bitCount;
   let target = 1;
   while (target < min)
   target *= 2;
   if (target > n)
   return −1;
   if (target == min)
   return A.map((c, p) => [1 << Number(p), c]);
   if (target == n)
   return [n];
   target = target − min;
   let i = m ? maximum : p;
   while (target && i > 0){
      if (!A[i]){
         i −= 1;
         continue;
      }
      const max = Math.min(target, A[i]);
      A[i] −= max;
      A[i−1] += 2*max;
      target −= max;
      i −= 1;
   }
   return target ? −1 : A.map((c, p) => [1 << Number(p), c]);
};
console.log(permuteCombinations(11, 5));

出力結果

コンソールには次のように出力されます。

[ [ 1, 1 ], [ 2, 1 ], [ 4, 2 ], [ 8, 0 ], [ 16, 0 ], [ 32, 0 ] ]

出力の読み方

この出力は「[チャンクのサイズ, 個数]」のペアを表しています。つまり、サイズ1のチャンクが1個、サイズ2のチャンクが1個、サイズ4のチャンクが2個という意味です。合計すると 1×1 + 2×1 + 4×2 = 11 となり、チャンクの総数は 1 + 1 + 2 = 4 で、2の累乗という条件も満たしています。

このように、まず最大サイズ（2のmaximum乗）でできるだけ多くのチャンクを作り、残りをビット演算で分解したうえで、必要に応じて大きなチャンクを2つずつの小さなチャンクへ分割していくことで、条件を満たす組み合わせを効率的に求められます。条件を満たす分割が存在しない場合は −1 が返されます。