Phân hoạch N với số phần và kích thước mỗi phần là lũy thừa của 2 trong JavaScript

Viết hàm chia số thành các khối theo quy tắc: số khối là lũy thừa 2, mỗi khối cũng có kích thước lũy thừa 2 (max 32).

Ví dụ: 8 → [8]; 9 → [8,1]; 11 → [4,4,2,1] (4 khối - lũy thừa 2).

Ví dụ

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, 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));

Kết quả

Kết quả in ra console (dạng [kích_thước, số_lượng]):

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