JavaScriptで配列のすべてのサブセット（部分集合）を求める方法

はじめに

JavaScriptで配列（集合）のすべてのサブセット（部分集合）を求めるには、reduce()メソッドとmap()メソッドを組み合わせるのが効果的です。この記事では、実際のコード例を使ってその手順をわかりやすく解説します。

サブセットを求める考え方

n個の要素を持つ配列のサブセットの総数は 2ⁿ 個になります。例えば、[8, 9] のように要素が2つあれば、空の配列を含めて4つのサブセットが生成されます。処理の流れは以下の通りです。

• 初期値として、空の配列を1つだけ含む配列 [[]] を用意します。
• 元の配列から要素を1つずつ取り出し、既存の各サブセットにその要素を追加した新しいサブセットを作成します。
• 既存のサブセットと新しく作成したサブセットを連結しながら処理を繰り返し、最終的にすべての組み合わせを取得します。

コード例

const findAllSubsetsoOfGivenSet =
originalArrayValue => originalArrayValue.reduce(
    (givenSet, setValue) => givenSet.concat(
        givenSet.map(givenSet => [setValue, ...givenSet])
    ),
[[]]
);
console.log(findAllSubsetsoOfGivenSet([8, 9]));

上記のプログラムを実行するには、Node.js環境で以下のコマンドを使用します。

node demo36.js

ここでは、ファイル名を demo36.js として保存しているものとします。

実行結果

プログラムを実行すると、コンソールに次のような出力が表示されます。

PS C:\Users\Amit\JavaScript-code> node demo36.js
[ [], [ 8 ], [ 9 ], [ 9, 8 ] ]

このように、空の配列を含む4つのサブセットが出力されました。要素の並び順は処理の流れによって変わることがあり、[9, 8] のような順序で表示される場合もありますが、これも正しいサブセットの1つです。