Clever Geek Handbook

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

There is often a problem when property A can be either true or false, property B is also true or false, etc. We want to check that each combination of A is true and B is false, and so on. 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 with a list function.

My question is, what's the easiest and / or fastest way to create this? I've always done this by converting the number to binary and then converting the binary to an array. But this seems cumbersome because the decimal to binary conversion is not completely trivial, and we also need to worry about padding the binary with leading zeros in order to properly populate the array.

I've implemented and reimplemented a feature like this in different contexts long enough to wonder if there is a simple enough way that you can implement it from scratch when needed - without having to think?

+3


source to share


4 answers


I'm not entirely sure about 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 repeat the digits 0 through 7 (000 through 111 respectively) and emphasize each bit to identify a boolean value.

+5


source


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);
}
+3


source


Try it -

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 method is widely used by competing programmers.

+1


source


The easiest way is to use next_permutation 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;
}
-1


source






More articles:


All Articles