There quite a few definitions of what a **set** is, but it all boils down to this:

A **set** defined as a collection of *distinct* elements, in which order is not important.

So *{1, 2, 3}*, *{3, 4}*, *{}* and *{5, 99, -1}* are all sets. Because the order of the elements is ignored, *{1, 2, 3}* and *{3, 2, 1}* is the same set. In case you’re wandering, there are exactly *n!* diffrent ways to write a set of *n* elements.

For the rest of the discussion, I’ll use sets of the form *{1, 2, …, n}*, so when I say a set of *3* elements, I mean *{1, 2, 3}*. Just remember that is **not** a property of sets. They can contain anything as elements, not necessarily consecutive numbers.

The set *S _{1}* is said to be the

**subset**of the set

*S*, if all the elements of

_{2}*S*also belong to

_{1}*S*.

_{2}Knowing this, it’s easy to figure out the subsets of *{1, 2, 3}*:

*{ }
{ 1 }
{ 2 }
{ 1, 2 }
{ 3 }
{ 1, 3 }
{ 2, 3 }
{ 1, 2, 3 }*

How many subsets are there? For a set of *one* element, there are *2* subsets: *{}* and *{1}*. For a set of *2* elements, there are *4* subsets: *{}*, *{1}*, *{2}*, *{1, 2}*. For a set of *3* elements, there are *8* subsets. Notice the pattern?

`n = 1: 2`

^{1}

n = 2: 2^{2}

n = 3: 2^{3}

For a set of *n* there are *2 ^{n}* subsets. This is easily proved: Any subset of the set can either contain or not contain an element; so, for a subset, there are

*2*states for the first element,

*2*for the second element, …,

*2*for the

*n*element; so, there are

^{th}*2*states for the first element,

*2 * 2 = 2*states for the first two,

^{2}*2 * 2 * 2= 2*states for the first three, …,

^{3}*2 * 2 * 2 * … * 2 = 2*states for all the

^{n}*n*elements.

The problem here is how to generate all the subsets of a given set. There are a few algorithms for doing this, but in the end, only two are worth considering.

The first is this: given all the subsets of *S* and the element *y*, you can generate all the subsets of *S U {y}* by taking each subset of *S*, once adding to it *y* and once leaving it as it is. **i.e.** Knowing that *{1, 3}* is a subset of *S*, you obtain the following two subsets of *S U {y}*: *{1, 3, y}* and *{1, 3}*.

This does what it’s supposed to – it generates all the subsets of *S*, and it wastes no time. It can also be used as another way to prove that there are *2 ^{n}* subsets for any set of

*n*elements. The only problem is that you need the subsets from the previous step to generate those of this step. This means that just before the end, you must have

*2*subsets in memory. Considering how much memory computers have this days, it’s not particularly wasteful, but still, there’s a better way.

^{n – 1}The better way involves using a **mask**. If you have the a set of *n* elements, a valid mask would be an array of *n* boolean (true/false; 1/0) elements. When you apply a mask to a set, you check each element *(e)* in the set and the corresponding one in the mask *(m)*: if *m* is true(1), you add *e* to the result, otherwise, you ignore it. After applying the mask *(0, 1, 0, 0, 1)* to *{1, 2, 3, 4, 5}*, you get *{2, 5}*.

So, to generate all the subsets of a set of *n* elements, you first have to generate all the possible *2 ^{n}* masks of the set and then apply them.

Generating the masks is a simple problem. Basically, you just have to implement a **binary counter**, i.e. something that generates:

`000`

001

010

011

100

101

110

111

Here’s the code in C (sub.c):

#include <stdio.h> /* Applies the mask to a set like {1, 2, ..., n} and prints it */ void printv(int mask[], int n) { int i; printf("{ "); for (i = 0; i < n; ++i) if (mask[i]) printf("%d ", i + 1); /*i+1 is part of the subset*/ printf("\\b }\\n"); } /* Generates the next mask*/ int next(int mask[], int n) { int i; for (i = 0; (i < n) && mask[i]; ++i) mask[i] = 0; if (i < n) { mask[i] = 1; return 1; } return 0; } int main(int argc, char *argv[]) { int n = 3; int mask[16]; /* Guess what this is */ int i; for (i = 0; i < n; ++i) mask[i] = 0; /* Print the first set */ printv(mask, n); /* Print all the others */ while (next(mask, n)) printv(mask, n); return 0; }

Note: The `next()`

function generates the bits in **reverse** order.

Always open to comments.

2007-10-12 at 11:58

Thank you so much. I was trying to catch a deadline for a project. I implemented your code and it worked perfect. Compared to other source in the internet simple and very well writen! Thanks!

UC Davis, CA

2007-10-28 at 4:41

[…] story here This entry was posted on Wednesday, October 10th, 2007 at 8:45 am and is filed under computer […]

2007-12-18 at 16:21

What complexity does this algorithm have?

2007-12-31 at 19:42

Complexity is O(N). This can easily be proven using Amortized Analysis.

2008-05-30 at 6:51

thnx man its awesome .the concept is wowwwww

2008-09-13 at 10:48

thank you

2008-10-04 at 1:00

O(n)? oh dear, sure it isn’t…

2009-01-12 at 20:03

Is there a code that will generate the following patterns, given {a,b,c,d,e}

a,b,c,d,e

ab,c,d,e

a,bc,d,e

a,b,cd,e

a,b,c,de

abc,d,e etc.?

Note that all these patterns use all the components and furthermore the order is always preserved ie ac,b,d,e is not allowed.

2009-02-18 at 18:18

Thanks

it done well

2009-03-06 at 19:17

It isnt O(n), since you are generating 2^n subsets

hence it is O( 2^n )

2009-03-18 at 19:23

Depending on what you want to do with the subsets, a Gray code (http://en.wikipedia.org/wiki/Gray_code) can be a significant improvement. The idea is that it is possible to construct the masks so that at each step, the mask only changes in one spot.

For example, if you are trying to find the largest set without x,y,z such that x+z=2y (i.e., a set without 3 evenly space numbers), then a Gray code would allow you to only check for triples involving the new element.

In my experience, unfortunately, the overhead of managing the more complicated ordering of masks outweighs the advantage of Gray codes for reasonable values of n.

2009-04-12 at 8:26

thank you

2009-07-19 at 2:14

nice! i’m gonna make my own blog

2009-09-17 at 11:19

it is not a c code i need a c code so can u sub mit c code

2009-09-17 at 11:25

what does < mean in u r program

2009-09-17 at 15:17

what does for(i = 0; (i < n) && mask[i]; ++i)mean

2009-11-06 at 18:58

[…] Generating subsets Filed under: Uncategorized — tuxdna @ 3:52 pm https://compprog.wordpress.com/2007/10/10/generating-subsets/ […]

2009-12-05 at 17:54

thank you for nice solved problem. I need it to make brute force for task scheduling on 2 CPU’s.

Best regards,

Lexus

2009-12-05 at 18:23

btw: have you ever hear about pointers and reference? :)

2010-06-08 at 19:02

Thanks…

That’s the sollution!

2010-10-11 at 11:52

can you kindly transfer code from c to

c++ or JAVA ,

Thanks in advance.

2011-04-22 at 20:43

This program can be transferred to C++ without much changes.

#include

using namespace std;

int const size=4;

void printv(int (& mask)[size], int (& a)[size])

{

int i;

cout<<"{";

for (i = 0; i < size; ++i)

if (mask[i]) cout << a[i]<<' ';

cout << "}";

}

/* Generates the next mask*/

int next( int (& mask)[size] )

{

int i;

/*

for(i=0; i< size; ++i)

cout << mask[i];

cout << endl;

*/

for (i = 0; (i< size) && mask[i]; ++i)

mask[i] = 0;

if (i < size)

{

mask[i] = 1;

return 1;

}

return 0;

}

int main() {

int mask[size]; /* Guess what this is */

int i, a[size];

unsigned int total=1;

for (i = 0; i < size; ++i)

{ a[i]=i+1; mask[i] = 0; total=2*total;}

/* Print the first set */

printv(mask, a);

/* Print all the others */

while (next(mask))

printv(mask, a);

cout << endl;

cout << "there are totaly " << total << " subsets. \n";

return 0;

}

2011-04-29 at 10:05

Generating mask can be actually more simple.

list = range(2)

for x in list:

for y in list:

for z in list:

print x, y, z

The python code above outputs:

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

2011-08-22 at 12:17

Check this out….

function getSubSets(setT)

{

var subSets = [];

for(var i = 0; i 0; k++)

{

var r = n%2;

if(r == 1)

subSets[i][subSets[i].length] = setT[k];

n -= r;

n = n/2;

}

}

return subSets;

}

2011-08-22 at 12:19

Missed something

function getSubSets(setT)

{

var subSets = [];

for(var i = 0; i 0; k++)

{

var r = n%2;

if(r == 1)

{

subSets[i][subSets[i].length] = setT[k];

}

n -= r;

n = n/2;

}

}

return subSets;

}

2011-11-02 at 18:00

this code generates lots of compilation errors.

look in line 07,16,19and 31

what is lt and & in your code?

2011-12-19 at 7:29

the “<” and “&” are the html entities for “<" and "&" respectively.

2011-12-19 at 7:35

& amp; :: &

& lt; :: <

2011-11-21 at 3:51

russian art movements…[…]Generating Subsets « Computer programming[…]…

2011-11-21 at 3:52

internet marketing tools,marketing tools and software…[…]Generating Subsets « Computer programming[…]…

2011-12-02 at 2:12

warez…[…]Generating Subsets « Computer programming[…]…

2011-12-09 at 7:48

Your blog is pretty interesting to me and your topics are very relevant. I was browsing around and came across something you might find interesting. I was guilty of 3 of them with my sites. “99% of blog managers are guilty of these 5 errors”. http://is.gd/8kynyd You will be suprised how easy they are to fix.

2012-01-08 at 14:26

good explanation

2012-02-28 at 22:06

Thanks!

2012-05-13 at 1:57

Wow…..perfect….Thank you

2012-05-19 at 15:58

Hello I have a one question regarding using a mask. In main function I changed the number from 16 to 2, so- int mask[16]; -> int mask[2] and it wroked properly. So should not be the size of the array the number of elemenst-1 instead of possible permutations? I mean- if the given set is {1,2,3,4}, int mask would be 3, because we need only 3 elemenst (or digits) to count all possible permutations. Even if we have 4 numbers, we dont need 4 elements in mask, because there is only one permutation that use all 4 numbers, so we dont need to count it. I hope it is not very chatic… Thanks a lot

2012-06-17 at 6:05

Great example scvalex. I was looking for ways to generate all possible subsets for a problem I was working on, and using a bitmask works perfectly (and is much easier to understand than recursive subset implementations)!

2012-07-11 at 21:13

This is the php version with a little improvement which remove generating the masks.

function printv(&$set, $mask){

$len = count($set);

$str = ‘[ ‘;

for($i = 0 ; $i > $i) & 1){

$str .= $set[$i] . ‘ ‘;

}

}

$str .= ‘]’ . “\n”;

echo $str;

}

function printAllSubsets($set){

$len = pow(2, count($set));

for($i = 0; $i < $len; $i++){

printv($set, $i);

}

}

//$set = range(0,29);

//printAllSubsets($set);

2013-04-02 at 17:33

In the awesome scheme of things you’ll get a B+ just for hard work. Exactly where you actually lost us was in the particulars. You know, people say, the devil is in the details… And that could not be much more true at this point. Having said that, let me tell you just what exactly did deliver the results. Your authoring is definitely highly engaging and that is probably why I am taking the effort in order to opine. I do not make it a regular habit of doing that. 2nd, even though I can certainly see a jumps in reasoning you come up with, I am not really certain of just how you seem to connect your points which in turn help to make the actual final result. For the moment I will, no doubt subscribe to your issue however trust in the near future you actually link your dots much better.

2013-04-09 at 21:20

A motivating discussion is worth comment. I think that you need to publish more on this issue, it may not be a taboo subject but usually folks don’t speak about such issues. To the next! Best wishes!!