Finding All the Subsets of a Set

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 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]));

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

Is there any algorithm to generate all subsets of a given set in O(n^2) time?

If you want to for example print all the subsets or store them explicitly anywhere there is no such algorithm. Notice that there are 2^n subsets of a set of n elements and simply enumerating them requires an exponential time.

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 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.



Related Topics



Leave a reply



Submit