부품 및 각 부품의 개수가 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 ] ]