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
- Powerset of
{3}
is3
combined with{{}}
={ {}, {3} }
;
- Remove
- Powerset of
{2, 3}
is{2}
combined with{ {}, {3} }
={ {}, {3}, {2}, {2, 3} }
;
- Remove
- 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
What Are the Advantages of Using Nullptr
Direct Way of Computing Clockwise Angle Between 2 Vectors
Advantages of Using Std::Make_Unique Over New Operator
What's Your Favorite Profiling Tool (For C++)
Vector of Vectors to Create Matrix
How to Automatically Convert Strongly Typed Enum into Int
In C/C++ What's the Simplest Way to Reverse the Order of Bits in a Byte
How to Detect C++11 Support of a Compiler With Cmake
How to Use Reference Parameters in C++
Calculating Normals in a Triangle Mesh
"X Does Not Name a Type" Error in C++
How Do Conversion Operators Work in C++
Throw Keyword in Function'S Signature
How to Get the Error Message from the Error Code Returned by Getlasterror()
What Are the Best (Portable) Cross-Platform Arbitrary-Precision Math Libraries
How to Remove an Item from a Stl Vector With a Certain Value