Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Is there an algorithm to calculate this?

share|improve this question
8  
Is the set finite? –  Quinn Culver Apr 2 '13 at 16:24
3  
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
2  
In general, there is not even an algorithm to find all elements of a set. –  Hagen von Eitzen Apr 2 '13 at 16:29
    
show 1 more comment

8 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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}
share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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)]
share|improve this answer
add comment

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}, {}

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

source: http://www.stanford.edu/class/archive/cs/cs106b/cs106b.1126/lectures/07/Slides07.pdf

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.