How to find the number of non-empty subsets in JavaScript

Given an element of a sequence, which consists of numbers or characters and may have repeated values, how to find the number of non-empty subsets?

For example, there is the sequence {1, 2, 3, 4}, and its non-empty subsets include:

{{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}}etc 15 items, and the empty set is not included in the statistics.

Another example is the sequence {a, b, c, d, d}, which has repeated values ​​inside it, but because the set is not repeatable, Therefore its non-empty subset includes:

{{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}}, which is also the 15 item, and the duplicate d has been removed.

The traditional subsetting method may not be useful in this problem, because of the performance requirements, the length of the sequence may reach 50 or even more, If you use recursion, it will take too long.

Fortunately, we do not need to ask for the specific content of the subset, only the number, so we can use a formula.

If a set (note not a sequence) has N elements, then it has 2 ##Nth power subset. This subset contains the empty set and itself, so if you want a non-empty subset, you can use 2^N - 1 to calculate.

Okay, here, this problem can be divided into 2 steps:

1. Deduplicate the sequence

2. Use formula to calculate the number of non-empty subsets

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;
}

The above is the detailed content of How to find the number of non-empty subsets in JavaScript. For more information, please follow other related articles on the PHP Chinese website!