Calculating All of the Subsets of a Set of Numbers

Calculating all of the subsets of a set of numbers

What you want is called a Powerset. Here is a simple implementation of it:

public static Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
        Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
        if (originalSet.isEmpty()) {
            sets.add(new HashSet<Integer>());
            return sets;
        }
        List<Integer> list = new ArrayList<Integer>(originalSet);
        Integer head = list.get(0);
        Set<Integer> rest = new HashSet<Integer>(list.subList(1, list.size()));
        for (Set<Integer> set : powerSet(rest)) {
            Set<Integer> newSet = new HashSet<Integer>();
            newSet.add(head);
            newSet.addAll(set);
            sets.add(newSet);
            sets.add(set);
        }
        return sets;
    }

I will give you an example to explain how the algorithm works for the powerset of {1, 2, 3}:

Remove {1}, and execute powerset for {2, 3};
- Remove {2}, and execute powerset for {3};
  - Remove {3}, and execute powerset for {};
    - Powerset of {} is {{}};
  - Powerset of {3} is 3 combined with {{}} = { {}, {3} };
- Powerset of {2, 3} is {2} combined with { {}, {3} } = { {}, {3}, {2}, {2, 3} };
Powerset of {1, 2, 3} is {1} combined with { {}, {3}, {2}, {2, 3} } = { {}, {3}, {2}, {2, 3}, {1}, {3, 1}, {2, 1}, {2, 3, 1} }.

How do you calculate the total number of all possible unique subsets from a set with repeats?

Take the product of all the (frequencies + 1).

For example, in {A,B,B}, the answer is (1+1) [the number of As] * (2+1) [the number of Bs] = 6.

In the second example, count(A) = 2 and count(B) = 2. Thus the answer is (2+1) * (2+1) = 9.

The reason this works is that you can define any subset as a vector of counts - for {A,B,B}, the subsets can be described as {A=0,B=0}, {A=0,B=1}, {0,2}, {1,0}, {1,1}, {1,2}.

For each number in counts[] there are (frequencies of that object + 1) possible values. (0..frequencies)

Therefore, the total number of possiblities is the product of all (frequencies+1).

The "all unique" case can also be explained this way - there is one occurence of each object, so the answer is (1+1)^|S| = 2^|S|.

How can I find all the subsets of a set, with exactly n elements?

itertools.combinations is your friend if you have Python 2.6 or greater. Otherwise, check the link for an implementation of an equivalent function.

import itertools
def findsubsets(S,m):
    return set(itertools.combinations(S, m))

S: The set for which you want to find subsets

m: The number of elements in the subset

Finding all the subsets of a set

It's very simple to do this recursively. The basic idea is that for each element, the set of subsets can be divided equally into those that contain that element and those that don't, and those two sets are otherwise equal.

For n=1, the set of subsets is {{}, {1}}
For n>1, find the set of subsets of 1,...,n-1 and make two copies of it. For one of them, add n to each subset. Then take the union of the two copies.

Edit To make it crystal clear:

The set of subsets of {1} is {{}, {1}}
For {1, 2}, take {{}, {1}}, add 2 to each subset to get {{2}, {1, 2}} and take the union with {{}, {1}} to get {{}, {1}, {2}, {1, 2}}
Repeat till you reach n

How does this code count all subsets of a set of positive integers whose sum is even?

This does not need an iterative program at all. Suppose your set has N elements, k even, and N-k odd. Then, the k even numbers are not really relevant; any of the 2^k combinations of them, together with the subsets of the odd numbers with even sums, combines to an even sum.

How many combinations of the odd numbers have even sum? If N-k > 0, there are 2^(N - k - 1) of them. So, you are right. This is a coding problem and not a math problem.

But the given algorithm is as follows:

When N = 0, there is only one subset of the set: the empty set, which sums to 0. So, start with even=1 and odd=0. Now the inductive step: suppose the numbers of partitions for the first k elements are even and odd.

If the k+1-th number is even, than any subset of the first k whose sum is even can have the k+1-th element appended (or not), doubling the number of even subsets. The same applies for the subsets with odd sums.

If the k+1-th number is odd, then any subset of the first k numbers whose sum is even does not give any new even subsets with the k+1-th number, while the a subset of the first k numbers whose sum is odd gives one with an even sum if the k+1-th is appended. So, the new even is the sum of the old even and odd. Similarly, the new odd is also the same sum, so the new odd equals the new even.

Note that even + odd == 2^k for all k, no matter what. And, once there is an odd number, even == odd for that index and all higher.

How to get subsets of a set with given number of elements in C with recursion?

This should do the job:

void subset(int n, int k, int B[], int i) {
    if (k == 0) {
        for (int d = 0; d < n; d++) {
            printf("%d ", B[d]);
        }
        printf("\n");
    } else if (i >= n || k > n - i) {
        return;
    } else {
        B[i] = 1;
        subset(n, k - 1, B, i + 1);
        B[i] = 0;
        subset(n, k, B, i + 1);
    }
}

int main(int argc, char **argv) {
    int n, k;
    int B[4];

    memset(B, 0, sizeof(B));
    n = sizeof(B) / sizeof(B[0]);
    k = 2;
    printf("n=%d\nk=%d\n", n, k);
    subset(n, k, B, 0);
    return 0;
}

How to get all subsets of a set? (powerset)

The Python itertools page has exactly a powerset recipe for this:

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

Output:

>>> list(powerset("abcd"))
[(), ('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')]

If you don't like that empty tuple at the beginning, you can just change the range statement to range(1, len(s)+1) to avoid a 0-length combination.

Calculating combinations of subsets of given size leading up to the set

How about creating the combinations of length 2, and generate the remainder by computing the difference from the original set? Here's what I mean:

from itertools import combinations

s = {'a', 'b', 'c'}

res = [(set(comb), s.difference(comb)) for comb in combinations(s, 2)]

Generates:

[({'a', 'c'}, {'b'}), ({'b', 'c'}, {'a'}), ({'a', 'b'}, {'c'})]

How to find all subsets of a set in JavaScript? (Powerset of array)

Here is one more very elegant solution with no loops or recursion, only using the map and reduce array native functions.

const getAllSubsets =       theArray => theArray.reduce(        (subsets, value) => subsets.concat(         subsets.map(set => [value,...set])        ),        [[]]      );
console.log(getAllSubsets([1,2,3]));

Determine all consecutive subsets of the set {1,2,3,…,n}. The subsets should have at least 2 elements

We already know the answer for these cases (as you wrote in your examples):

For n=5:

You can partition from 2: 1 2 - 3 4 5. This is like dividing the 5 member set into two sets, first one n=2, and second one n=3. We can now continue dividing each half, but we already know the solutions when n=2 and n=3!
You can partition from 3: 1 2 3 - 4 5. This is like dividing the 5 member set into two sets, first one n=3, and second one n=2. We can now continue dividing each half, but we already know the solution when n=2 and n=3!

For n=6:

You can partition into two sets from 2: 1 2 - 3 4 5 6. This is like dividing the 6 member set into two sets, first one n=2, and second one n=4. We can now continue dividing each half, but we already know the solution when n=2. Solve the second half by assuming n=4!
You can partition into two sets from 3: 1 2 3 - 4 5 6. This is like dividing the 6 member set into two sets, first one n=3, and second one n=3, We can now continue dividing each half, but we already know the solution when n=3 and n=3!
You can partition into two sets from 3: 1 2 3 4 - 5 6. This is like dividing the 6 member set into two sets, first one n=4, and second one n=2, We can now continue dividing each half. Solve the first half by setting n=4. For the second half, we already know the solution when n=2!

This is a simple recursion relationship. The general case:

Partition (S): (where |S|>4)
- For i from 2 to |S|-2, partition the given set into two halves: s1 and s2 from i (s1={1,...,i}, s2={i+1,...,n}), and print the two subsets as a solution.
- Recursively continue for each half by calling Partition(s1) and Partition(s2)

---

Another perhaps harder solution is to assume we are dividing the numbers 1 to n into n sections, where the length of each section can be either 0, 2, or a number greater than 2. In other words let xi be the length of each section:

x1 + x2 + ... xn = n, where the range of xi is: {0} + [2,n]

This is a system of linear non-equalities can can be solved by methods described here.

Calculating All of the Subsets of a Set of Numbers