Generate all ways of selection of n items [duplicate]

This question already has answers here: Closed 11 years ago.

Possible Duplicate:

How to find all possible subsets of a given array?

How can all ways of selection of items be generated efficiently using C++?

For example, if there are there items A, B and C.

[A,B,C] => [A], [B], [C], [A,B], [B,开发者_运维问答C], [A,C], [A, B, C]

---

For that input set:

#include <iostream>

void print(int b, char *a, int n)
{
   for(int i = 0 ; i < n ; i++)
   {
     if( b & 0x1)  std::cout << a[i];
     b = b >> 1;
   }
   std::cout << std::endl; 
}

int main() {
        char a[] = {'A','B','C'};
        for(int i = 1 ; i < 8 ; i++ )
            print(i,a,3);
        return 0;
}

Output:

A
B
AB
C
AC
BC
ABC

Demo : http://ideone.com/2Wxbi

Now it's your turn to improve and generalize this approach, and find it's limitations.

---

Essentially, you can break the problem down into: "For each item, will it be part of the set or not". If you can find all combinations of that then you can find all possible ways of selecting items.

A way of representing whether an item is in the set or not is with a Boolean. True or 1 if it is in the set and false or 0 if it isn't. So we need a Boolean for each of the items. This brings to mind an int or another type as they are all essentially, a bunch of bits.

Now how can we find all combinations of those booleans. There is a simple answer: loop through all the integers. For example:

ABCD Number in base 10
0000 0
0001 1
0010 2
0011 3
0100 4
.... ...
1111 (2^4) - 1

We know there are 2^4 answer since each item can be in the set or not in the set so there are 2 possibilities for each item. If there are 4 element then there are 2*2*2*2 or 2^4 combinations.

There's also an easy way to find 2^n. Simply doing 1 << n.

This leads us to the simple answer:

for (int i = 0; i < (1 << n); i++) {
    // Here the ath bit of i will be set if the ath item is part of the set
} 

Note that this will include the empty set, ie [ ]. If you don't want this, simply start the loop from 1 instead of 0.

Hope this helps.

---

If you have N elements (here N=3), then iterate i from 1 to (1<<3) and in each iteration look at binary value of i.