パーツの数と各パーツが2の累乗であり、パーツのサイズと数がJavaScriptで制限されているパーティションN

数値を取り込むJavaScript関数を作成する必要があります。関数は、次のルールに従って数値をチャンクに分割する必要があります-

• チャンクの数は2の累乗である必要があります

• 各チャンクには、2の累乗の数のアイテムも必要です（サイズは最大2の累乗になるため、1、2、4、8、16、32、32が最大になります）

したがって、たとえば、8つを1つのバケットに分割できます-

[8]

9は-

[8, 1]

これは、両方の数値が2の累乗であり、配列のサイズが2（これも2の累乗）であるために機能します。

11を試してみましょう-

[8, 2, 1]

いいえ、機能しません。

配列のサイズは3であるため、11に追加されますが、2の累乗ではありません。

[4, 4, 2, 1]

それはうまくいきます！ 2の累乗である4つの要素です。

例

このためのコードは-

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 ] ]