Thread: Obtaining all combinations of elements...

Are you sure you want {{1},{2},{1,2}}, and not {{},{1},{2},{1,2}}? The latter is the power set.

There are several ways to acquire a power set. One is to use the bits of an integer to select elements of an array. For example, if your array is [x0,x1,x2,x3,x4] and your selection mask is 13 (which is 1101 in binary), then your subset will be

Code:

x0 x1 x2 x3 x4
1  0  1  1  0    <- these bits are 01101 reversed
x0    x2 x3

Note that the bits in the diagram above are reversed, so that the 'zeroth' bit (with value 2 to the zero power) lines up with the zeroth element of the array, x0.

So, to generate all the subsets of [x0,x1,x2,x3,x4], start your bit mask at 0, and loop until your bit mask is equal to 32, and use that to mask the elements of the array.

Something like the following. This code uses vectors, since I don't feel like dealing with manual allocation for the multidimensional arrays.

Code:

vector<int> vec;
/* initialize vec */

vector<vector<int> > power_set; 

int im = 4; /* num elements in vec */
for (i = 0; i < im; ++i) {
  power_set.push_back(mask_elements(i, vec));
}

where mask_elements is a function that performs the operation above. That requires another for loop, in which you loop through the bits of the integer, selecting elements of the vector (push_back()ing them onto the return value) whenever you come across a bit that is 1. You can do that using (1 << k) to generate a number that is 2 to the kth power, or some other trick.

If you want to avoid the empty set (if you do not want the 'true' power set), start with i=1, instead of i=0, and then the empty set won't be included.