หาทุกวิธีการแยกส่วนจำนวนเต็ม (Integer Partition) ใน JavaScript

Integer Partition คืออะไร

การแยกส่วน (Partition) ของจำนวนเต็มบวก n คือ การเขียน n เป็นผลรวมของจำนวนเต็มบวก สองวิธีที่ต่างกันแค่ลำดับถือว่าเป็น partition เดียวกัน

ตัวอย่าง n = 4

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

มีทั้งหมด 5 วิธี (p(4) = 5)

โค้ดตัวอย่าง (Dynamic Programming - นับจำนวน)

const findPartitions = (num = 1) => {
  // DP table: arr[i][j] = จำนวนวิธีแยกส่วน j ด้วยจำนวนสูงสุด i
  const arr = Array(num + 1).fill(null).map(() => 
    Array(num + 1).fill(null));
  
  // Base cases
  for (let j = 1; j <= num; j++) arr[0][j] = 0;
  for (let i = 0; i <= num; i++) arr[i][0] = 1;
  
  // Fill DP table
  for (let i = 1; i <= num; i++) {
    for (let j = 1; j <= num; j++) {
      if (i > j) {
        arr[i][j] = arr[i - 1][j]; // ไม่ใช้ i
      } else {
        const exclusive = arr[i - 1][j]; // ไม่ใช้ i
        const inclusive = arr[i][j - i]; // ใช้ i (อาจใช้ซ้ำ)
        arr[i][j] = exclusive + inclusive;
      }
    }
  }
  return arr[num][num];
};

console.log(findPartitions(4)); // 5

ผลลัพธ์

5

โค้ดสร้าง Partition จริง (ไม่ใช่แค่นับ)

const generatePartitions = (n, max = n, prefix = [], result = []) => {
  if (n === 0) {
    result.push([...prefix]);
    return result;
  }
  
  for (let i = Math.min(max, n); i >= 1; i--) {
    prefix.push(i);
    generatePartitions(n - i, i, prefix, result);
    prefix.pop();
  }
  return result;
};

console.log(generatePartitions(4));
// [ [4], [3,1], [2,2], [2,1,1], [1,1,1,1] ]

เลข Partition Numbers (p(n))

ความซับซ้อน

• DP นับจำนวน: O(n²) Time, O(n²) Space
• Generate ทุกชุด: O(n × p(n)) - เติบโตแบบ exponential
• Euler's Pentagonal Number Theorem คำนวณ p(n) ได้ใน O(n√n)