I'm trying to find a way to find all subsets of a set.
Is there an algorithm to calculate this?
$\endgroup$ 710 Answers
$\begingroup$The algorithm in a recursive one. To understand the algorithm consider the following example:
Let $S = \{1,2,3\}$. The subsets of $S$ are all subsets of $\{1,2\}$ and all subsets of $\{1,2\}$ with the element $3$ appended to each subset. Essentially, if you know subsets of $\{1,2\}$, the problem can be solved. You can take it from here on.
$\endgroup$ 1 $\begingroup$An alternative to the recursive formulations provided so far to enumerate the subsets of a finite set is to index the subsets : if $n$ is the number of elements of your set, there are $2^n$ subsets. The subsets can be enumerated iteratively by using a variable index ranging from $0$ to $2^n-1$, and using the binary representation of the variable index to determine which elements of your base set the current subset has.
Over recursive formulations, this one has the advantage of not risking a stack overflow, which may happen if $n$ is greater than the stack capacity. It also avoids storing lists of subsets if you can process these subsets with a continuation.
$\endgroup$ 3 $\begingroup$In C, the algorithm explained by Vincent Nivoliers could look like:
int main(int size, char * set[]) { unsigned int i, j; unsigned short bit; unsigned int max_bits; // max bits for number i size = size - 1; // exclude first element for (i = 0; i < pow(2, size); i++) { printf("{ "); max_bits = floor( log2(i) ); for (j = 0; j <= max_bits; j++) { bit = (i >> j) & 1; // bit value at position j if (bit == 1) printf("%s ", set[j + 1]); // one-based array, add 1 } printf("}\n"); } return 0;
}which would for the arguments 1 2 3 produce the output
{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
{ 1 3 }
{ 2 3 }
{ 1 2 3 }The classic solution to this problem uses binary digits -- count from zero to $2^n-1$ where $n$ is the number of elements and for every value $k$ in the range include an element in the subset if the bit at position $q$ where $0\le q\le n-1$ is set.
Here is an implementation that prints all subsets of its command line arguments.
#! /usr/bin/perl -w
#
MAIN: { my $n = scalar(@ARGV); my (@flags) = (0) x $n; my $pos; while(1){ my @subset = (); for($pos=0; $pos<$n; $pos++){ push @subset, $ARGV[$pos] if $flags[$pos] == 1; } print '{' . join(', ', @subset) . '}'; print "\n"; for($pos=0; $pos<$n; $pos++){ if($flags[$pos] == 0){ $flags[$pos] = 1; last; } $flags[$pos] = 0; } last if $pos == $n; }
}This is what the output looks like:
$ ./subsets.pl a b c
{}
{a}
{b}
{a, b}
{c}
{a, c}
{b, c}
{a, b, c} $\endgroup$ 1 $\begingroup$ By identifying subsets with characteristic vectors, enumerating all subsets of an $n$-element set is the same as enumerating all binary vectors of length $n$.
One way is to enumerate the numbers $0,1,\ldots,2^n-1$ in binary notation. In many situations it is desirable to flip only a single bit going from one element to the next (correspondingly, going from one subset to the next by adding or removing only a single element). This can be achieved by the Gray code.
$\endgroup$ 2 $\begingroup$In a very simple speech, with binary codes you can discover all of them. for example if you want to write all subsets of a set with 2 member , you must calculate whole number from 0 to (2^2)-1 or 3. For instance: Suppose set : {1,2}
00 -----> 0 ---> {}
01 -----> 1 ---> {1}
10 -----> 2 ---> {2}
11 -----> 3 ---> {1,2}and you can continue this to end.
$\endgroup$ $\begingroup$Considering the set to be finite with $n$ elements in them.
Let $A$ = $(a_1, a_2,...a_n$)
Now you can have subsets of size $0$ to $n$ elements.
If the number of elements is ($n-1$) , subsets of $(n-1)$ element-ed sets are subsets of $A$ itself. This can be extended till $1$ element subsets.
Aliter:
You can make the $0,1, \dots n$ sets with the given elements.
$\endgroup$ $\begingroup$An algorithm is type of finite procedure operating on finite data as input and generating a finite output. So you can only have an algorithm to find the subsets of $\Sigma$ if $\Sigma$ is finite. (You've been given some hints for that case, but it is important to stress that these hints only work for finite $\Sigma$.)
$\endgroup$ $\begingroup$If I look into the problem in another perspective, this eventually boils down to
$$\sum_{k=0}^{|S|} {{|S|}\choose{k}}$$
And quickly solving in Python
>>> S = {1,2,3,4}
>>> from itertools import chain, combinations
>>> list(chain(*(list(combinations(S, n)) for n in range(0, len(S)+1))))
[(), (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)]First, you should notice that the only subset of an empty set is the empty set itself.
Then,
- Fix some element x of the set.
- Generate all subsets of the set formed by removing x from the main set.
- These subsets are subsets of the original set.
- All of the sets formed by adding x into those subsets are subsets of the original set.
Following is an illustration:
{ A, H, I}
{ H, I}
{ I}
{ }
now, we reach the base situation, namely empty set. Then, we will add the x that we have fixed into those subsets:
{ A, H, I} ------------------------> {A,H,I},{A,H},{A,I},{A}
{H,I},{H},{I},{}{ H, I} ------------------------> {H, I}, {H},
{I}, {}{ I} ------------------------> {I}, {}
{ } ------------------------> {}
source:
$\endgroup$
