Obtaining all combinations of elements...

Greetings. I am new to this board, but I'll try to be as clear as possible.

Here's the deal. Suppose I have the following array:

Code:

---

int old_array [] = {1,2}

---

I want to obtain a bidimensional array from that array, with the following elements:

Code:

---

{{1},{2},{1,2}}

---

Likewise, if I had:

Code:

---

int old_array [] = {1,2,3}

---

I'd want to obtain:

Code:

---

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

---

So, basically, I'm searching for an algorithm that allows me to obtain every single possible combination of elements from the old array: every combination of 1 element, every combination of 2 elements, and so forth.

Thus, I have two questions:

1) I know that what I want to obtain has a specific mathematical term in English, but what is that term exactly?

2) Do you happen to know how I can code such algorithm? If so, how?

Thank you in advance. I hope I've made myself clear enough.

I found the answer to my first question: what I am trying to do is to obtain the "power set" of my array. I can now rephrase my second question as:

Do you happen to know how I can obtain the "power set" of an array? If so, how?

1) Basically, you need the combinations of class k, where k is an integer from 0 to n, where n is the number of given elements.
2) Standard library supports permutations. Try to google for some library, maybe Boost (http://www.boost.org) has something.

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.