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項，而空集合並沒有統計在內。

再比如說有序列{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中文網其他相關文章！