CODEWITHSUNDEEP
c++algorithm
Lucky
Lucky

Reputation: 4839

What's the easiest way to generate a list of combinations in C++?

Oftentimes, you have a problem where property A can be either true or false, property B also either true or false, and so on. We want to test every combination of A being true while B being false, and so on. So for example we might need the following list:

[true,true,true]
[true,true,false]
[true,false,true]
[true,false,false]
[false,true,true]
[false,true,false]
[false,false,true]
[false,false,false]

In Haskell or Python, this can be done by a list product function.

My question is, what's the simplest and/or quickest way to generate this? I have always done this by converting a number to binary, then converting the binary into an array. But this seems cumbersome because decimal to binary conversion isn't completely trivial, and also we need to worry about padding the binary with leading zeroes to fill up the array properly.

I have implemented and re-implemented this kind of function in different contexts enough times to wonder, is there a way simple enough that you can implement it from scratch when necessary -- without really having to think?

Upvotes: 3

Views: 432

Answers (4)

XanderLynn
XanderLynn

Reputation: 883

The easiest way is to use next_permutation provided from STL. The following code is from cplusplus.com

// next_permutation
#include <iostream>
#include <algorithm>
using namespace std;

int main () {
  int myints[] = {1,2,3};

  cout << "The 3! possible permutations with 3 elements:\n";

  sort (myints,myints+3);

  do {
    cout << myints[0] << " " << myints[1] << " " << myints[2] << endl;
  } while ( next_permutation (myints,myints+3) );

  return 0;
}

Upvotes: -1

Sabbir Yousuf Sanny
Sabbir Yousuf Sanny

Reputation: 594

Try this - 

void allCombinations(int numVars) {
    for(int i = 0; i < (1<<numVars); i++) { //(1<<n) means 2^n
        for(int j = 0; j < numVars; j++) {
            if(i & (1<<j)) { //j-th variable value is true
                //do something
            }
            else { //j-th variable is false
                //do some other thing
            }
        }
    }
}

This technique is extensively used by contest programmers.

Upvotes: 1

Babak Naffas
Babak Naffas

Reputation: 12561

I'm not exactly sure of the code but something along these lines should work.

for( int i = 0; i < 8; i++ ){
  printf( "[%s, %s, %s]\n", (i & 0x1)?"True":"False", ((i & 0x2) >> 1)?"True":"False" , ((i & 0x4) >> 2)?"True":"False" );
}

I'm iterating through the numbers 0 to 7 (000 to 111 respectively) and isolating each bit to identify the boolean value.

Upvotes: 5

ElKamina
ElKamina

Reputation: 7807

Use recursion.

void f(x,i,n) {
  if (i<n) {
    x[i]=False;
    f(x,i+1,n);
    x[i]=True;
    f(x,i+1,n);
  }
  else print(x);
}

Upvotes: 3

Related Questions