JavaScript で空ではないサブセットの数を見つける方法

数値または文字で構成され、値が繰り返される可能性があるシーケンスの要素がある場合、空ではないサブセットの数を見つけるにはどうすればよいでしょうか?

たとえば、シーケンス {1, 2, 3, 4} があり、その空でないサブセットには次のものが含まれます:

{{1}, {2}, {3}, {4}, {1,2 }、{1,3}、{1,4}、{2,3}、{2,4}、{3,4}、{1,2,3}、{1,2,4 }、{1 ,3,4}、{2,3,4}、{1,2,3,4}} およびその他の 15 項目、および空のセットは統計に含まれません。

もう 1 つの例は、シーケンス {a, b, c, d, d} です。これは内部に繰り返し値を持ちますが、セットは繰り返し可能ではないため、空ではないサブセットには次のものが含まれます:

{ {a}、{b}、{c}、{d}、{a,b}、{a,c}、{a,d}、{b,c}、{b,d}、{c, d }、{a,b,c}、{a,b,d}、{a,c,d}、{b,c,d}、{a,b,c,d}}、また 15 個の アイテム、重複した d が削除されました。

再帰 を使用すると、シーケンスの長さが 50 以上に達する可能性があるため、サブセットを見つける従来の方法は役に立たない可能性があります。

幸いなことに、サブセットの特定の内容を尋ねる必要はなく、数値だけを尋ねる必要があるため、数式を使用できます。

集合 (シーケンスではないことに注意) に N 要素がある場合、 2 の N乗の部分集合を持ちます。このサブセットには空のセットとそれ自体が含まれているため、空でないサブセットが必要な場合は、 2^N を使用できます。 - 1を計算します。

この問題は 2 のステップに分割できます:

1. シーケンスを重複排除します

2 空でないサブセットの数を計算します

function estSubsets(arr) {
    var hash = {};
    for(var i=0;i<arr.length;i++){
        hash[arr[i]] = null;
    }
    arr = Object.keys(hash);
    return Math.pow(2,arr.length) - 1;
}

以上がJavaScript で空ではないサブセットの数を見つける方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。