หา Power Set (ชุดยกกำลัง) ของเซตใน JavaScript

Power Set คืออะไร

Power Set ของเซต S คือเซตของ ทุกเซตย่อย (Subsets) ของ S รวมถึงเซตว่างและ S เอง กำหนดสัญลักษณ์ว่า P(S)

ตัวอย่าง

ถ้า S = {x, y, z} เซตย่อยทั้งหมด 8 เซต:

{
  {},
  {x}, {y}, {z},
  {x, y}, {x, z}, {y, z},
  {x, y, z}
}

โค้ดตัวอย่าง (Bit Manipulation)

const set = ['x', 'y', 'z'];

const powerSet = (arr = []) => {
  const res = [];
  const { length } = arr;
  const numberOfCombinations = 2 ** length; // 2^n
  
  for (let combinationIndex = 0; combinationIndex < numberOfCombinations; combinationIndex++) {
    const subSet = [];
    for (let setElementIndex = 0; setElementIndex < arr.length; setElementIndex++) {
      // ตรวจสอบบิตที่ setElementIndex ใน combinationIndex
      if (combinationIndex & (1 << setElementIndex)) {
        subSet.push(arr[setElementIndex]);
      }
    }
    res.push(subSet);
  }
  return res;
};

console.log(powerSet(set));

ผลลัพธ์

[
  [], ['x'], ['y'], ['x', 'y'],
  ['z'], ['x', 'z'], ['y', 'z'], ['x', 'y', 'z']
]

วิธีอื่นๆ

1. ใช้ Recursive

const powerSetRecursive = (arr) => {
  if (arr.length === 0) return [[]];
  const [first, ...rest] = arr;
  const subsets = powerSetRecursive(rest);
  return [...subsets, ...subsets.map(set => [first, ...set])];
};

2. ใช้ Reduce

const powerSetReduce = (arr) => 
  arr.reduce((subsets, value) => 
    subsets.concat(subsets.map(set => [...set, value])), [[]]);

ความซับซ้อน

• Time: O(n × 2^n) - ต้องสร้าง 2^n เซตย่อย แต่ละเซตใช้ O(n)
• Space: O(n × 2^n) - เก็บทุกเซตย่อย
• เหมาะสำหรับ n ≤ 20 (ประมาณ 1 ล้านเซตย่อย)

การประยุกต์

• Combinatorial Optimization
• Subset Sum Problem
• Feature Selection ใน Machine Learning
• Game Theory (Coalition Formation)