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

リテラル値を要素とする配列を第1引数（唯一の引数）として受け取り、元の配列から生成できるすべての部分配列（サブセット）を含む配列を構築して返すJavaScript関数を作成します。

要件の確認

例えば、入力配列が次のような場合を考えてみましょう。

const arr = [1, 2, 3];

この場合、期待される出力は次のようになります。

const output = [
    [2],
    [1],
    [3],
    [1,2,3],
    [2,3],
    [1,2],
    [1, 3],
    []
];

なお、部分配列が出力される順序は特に問いません。n個の要素を持つ配列の部分集合は 2ⁿ 個存在するため、この例では 2³ = 8 個のサブセットが生成されます。

実装コード

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

const arr = [1, 2, 3];
const findAllSubsets = (arr = []) => {
    arr.sort();
    const res = [[]];
    let count, subRes, preLength;
    for (let i = 0; i < arr.length; i++) {
        count = 1;
        while (arr[i + 1] && arr[i + 1] == arr[i]) {
            count += 1;
            i++;
        }
        preLength = res.length;
        for (let j = 0; j < preLength; j++) {
            subRes = res[j].slice();
            for (let x = 1; x <= count; x++) {
                if (x > 0) subRes.push(arr[i]);
                res.push(subRes.slice());
            }
        }
    };
    return res;
};
console.log(findAllSubsets(arr));

コードの解説

このアルゴリズムのポイントは以下の通りです。

• まず sort() で配列をソートし、重複する要素を隣接させておきます。
• 結果を格納する res は空配列 [[]] からスタートします。
• 各要素について、連続して現れる重複の個数を count としてカウントします。
• 既存の各部分配列に対して、現在の要素を1回から count 回まで追加した組み合わせを新たに生成し、結果に追加していきます。

この処理により、配列内に重複した要素が含まれていても同一内容のサブセットが重複して生成されるのを防ぎながら、すべての可能な部分集合を効率的に列挙できます。

出力結果

コンソールへの出力は次の通りです。

[
    [], [ 1 ],
    [ 2 ], [ 1, 2 ],
    [ 3 ], [ 1, 3 ],
    [ 2, 3 ], [ 1, 2, 3 ]
]