# Is there an algorithm to find all subsets of a set?

I'm trying to find a way to find all subsets of a set.

Is there an algorithm to calculate this?

-
Is the set finite? –  Quinn Culver Apr 2 '13 at 16:24
Hint: in any given subset, each member of the base set is either in the subset or not in it. Can you think of a convenient way to map this to a digital representation? –  Steven Stadnicki Apr 2 '13 at 16:24
List them one by one? –  Hui Yu Apr 2 '13 at 16:26
In general, there is not even an algorithm to find all elements of a set. –  Hagen von Eitzen Apr 2 '13 at 16:29

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.

-

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.

-
While I didn't want to give a direct answer to what feels quite strongly like a homework question, this is a much better answer than any recursive or combination-based approach. –  Steven Stadnicki Apr 2 '13 at 16:56
@StevenStadnicki I fear the homework question as well, and tried not to be too descriptive, I hope this is not going too far. I had not read your comment when I started writing this, however all credit should go to you. –  Vincent Nivoliers Apr 2 '13 at 16:58

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}

-
This can also be done by directly counting to $2^n-1$ and extracting the bits of $k$ one after the other, but the idea is exactly the same. –  Marko Riedel Apr 2 '13 at 21:52

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.

-
I believe you mean $2^n-1$ rather than $n-1$ at the start of your second paragraph... –  Steven Stadnicki Apr 2 '13 at 22:31
@StevenStadnicki: Thanks for spotting this. It is corrected now. –  azimut Apr 3 '13 at 8:13

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.

-

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

-

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,

1. Fix some element x of the set.
2. Generate all subsets of the set formed by removing x from the main set.
3. These subsets are subsets of the original set.
4. 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}, {}

{ } ------------------------> {}

-