Obtaining all combinations of elements...

This is a discussion on Obtaining all combinations of elements... within the C++ Programming forums, part of the General Programming Boards category; Greetings. I am new to this board, but I'll try to be as clear as possible. Here's the deal. Suppose ...

  1. #1
    Registered User
    Join Date
    Nov 2006
    Location
    Coimbra, Portugal
    Posts
    64

    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.

  2. #2
    Registered User
    Join Date
    Nov 2006
    Location
    Coimbra, Portugal
    Posts
    64
    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?

  3. #3
    Registered User
    Join Date
    Jan 2006
    Location
    Europe/Belgrade
    Posts
    78
    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.

  4. #4
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    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.
    There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. using realloc for a dynamically growing array
    By broli86 in forum C Programming
    Replies: 10
    Last Post: 06-27-2008, 06:37 AM
  2. Randomly rearranging the elements in a vector
    By Signifier in forum C++ Programming
    Replies: 11
    Last Post: 08-01-2007, 01:21 PM
  3. way to check 3 elements of array and set 4th
    By Syneris in forum C++ Programming
    Replies: 3
    Last Post: 01-09-2006, 11:30 AM
  4. Replies: 2
    Last Post: 08-03-2003, 11:01 AM
  5. Combinations
    By GaPe in forum C Programming
    Replies: 16
    Last Post: 01-09-2002, 05:38 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21