การแบ่ง N โดยจำนวนส่วนและขนาดแต่ละส่วนเป็น Power of 2 ใน JavaScript

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่รับตัวเลข ฟังก์ชันควรแบ่งตัวเลขเป็น chunks ตามกติกา:

• จำนวน chunks ต้องเป็น power-of-two
• ขนาดแต่ละ chunk ต้องเป็น power-of-two (สูงสุด 32 คือ 1, 2, 4, 8, 16, 32)

ตัวอย่าง: 8 แบ่งเป็น 1 bucket: [8]

9 แบ่งเป็น: [8, 1] (ทั้งคู่เป็น power-of-two, จำนวน bucket = 2 ซึ่งเป็น power-of-two)

ลอง 11: [8, 2, 1] ไม่ได้ เพราะ 3 buckets ไม่ใช่ power-of-two

[4, 4, 2, 1] ได้! เพราะ 4 buckets เป็น power-of-two

ตัวอย่างโค้ด

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