13
$\begingroup$

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

Is there an algorithm to calculate this?

$\endgroup$
7
  • 9
    $\begingroup$ Is the set finite? $\endgroup$ Apr 2 '13 at 16:24
  • 3
    $\begingroup$ 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? $\endgroup$ Apr 2 '13 at 16:24
  • $\begingroup$ List them one by one? $\endgroup$
    – Hui Yu
    Apr 2 '13 at 16:26
  • 2
    $\begingroup$ In general, there is not even an algorithm to find all elements of a set. $\endgroup$ Apr 2 '13 at 16:29
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Power_set $\endgroup$ Apr 2 '13 at 16:34

10 Answers 10

14
$\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$ What is the name of this algorithm? $\endgroup$
    – user346461
    Jun 11 '16 at 19:52
7
$\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
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 2 '13 at 16:56
  • $\begingroup$ @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. $\endgroup$ Apr 2 '13 at 16:58
  • $\begingroup$ This is a common interview question. Got asked this twice already. Just leaving a note. $\endgroup$
    – ninja123
    Dec 30 '16 at 15:10
4
$\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 }
$\endgroup$
2
$\begingroup$

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$ 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. $\endgroup$ Apr 2 '13 at 21:52
2
$\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$ I believe you mean $2^n-1$ rather than $n-1$ at the start of your second paragraph... $\endgroup$ Apr 2 '13 at 22:31
  • $\begingroup$ @StevenStadnicki: Thanks for spotting this. It is corrected now. $\endgroup$
    – azimut
    Apr 3 '13 at 8:13
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$
0
$\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$
0
$\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$
0
$\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)]
$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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