JavaScriptで配列のべき集合（パワーセット）を求める方法

ある集合 S のべき集合（パワーセット）とは、S のすべての部分集合からなる集合のことです。空集合と S 自身も含まれ、P(S) という記号で表されます。

べき集合とは？具体例

たとえば、S = {x, y, z} の場合、部分集合は以下の8つになります。

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

要素数が n の集合に対して、べき集合の要素数は 2ⁿ 個になります。上の例では要素が3つなので、2³ = 8個の部分集合が存在するわけです。

JavaScriptでの実装方針

ここでは、配列を引数として受け取り、そのべき集合を返すJavaScript関数を作成します。

実装のポイントはビット演算です。各要素について「その部分集合に含めるかどうか」を0と1のフラグとして表現すると、0 から 2ⁿ − 1 までの整数が、すべての組み合わせパターンに対応します。この性質を利用することで、シンプルかつ効率的にべき集合を生成できます。

サンプルコード

以下が実際のコードです。

const set = ['x', 'y', 'z'];
const powerSet = (arr = []) => {
   const res = [];
   const { length } = arr;
   const numberOfCombinations = 2 ** length;
   for (let combinationIndex = 0; combinationIndex < numberOfCombinations; combinationIndex += 1) {
      const subSet = [];
      for (let setElementIndex = 0; setElementIndex < arr.length;
      setElementIndex += 1) {
         if (combinationIndex & (1 << setElementIndex)) {
            subSet.push(arr[setElementIndex]);
         };
      };
      res.push(subSet);
   };
   return res;
};
console.log(powerSet(set));

コードの解説

• numberOfCombinations: 要素数 n に対して 2ⁿ 通りの組み合わせが存在するため、これがループの総回数になります。
• combinationIndex & (1 << setElementIndex): ビットごとのAND演算により、現在の組み合わせインデックスにおいて該当位置のビットが立っているか（＝その要素を含めるか）を判定しています。
• subSet.push(...): ビットが立っている要素だけを部分集合に追加していきます。

実行結果

コンソールには次のように出力されます。

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

このように、空配列から元の配列そのものまで、合計8つの部分集合が正しく生成されていることが確認できます。ビット演算を用いたこの手法は、再帰を使わずにべき集合を求められるため、コードが簡潔になり、処理の流れも理解しやすいのが特徴です。