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

Question

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?

Loki Astari · Accepted Answer · 2012-03-07 00:35:22Z

5

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.

edited Mar 7, 2012 at 0:35

Loki Astari

267k87 gold badges344 silver badges575 bronze badges

answered Mar 7, 2012 at 0:06

Babak Naffas

12.6k3 gold badges36 silver badges51 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

vvnraman Over a year ago

The bit shifts are not required !!

Babak Naffas Over a year ago

@mwraman, you are correct. The shifts were from an original implementation where I was returning 0s and 1s.

Sabbir Yousuf Sanny Over a year ago

Will you write the code this way if number of variables is large, say 20? IMO, the question didn't specify that you have to write code for 3 variables.

ElKamina · Accepted Answer · 2012-03-07 00:08:35Z

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

Sabbir Yousuf Sanny · Accepted Answer · 2012-03-07 03:54:16Z

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.

XanderLynn · Accepted Answer · 2012-03-07 04:13:53Z

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; }

The question didn't ask for all permutations, rather all possible combinations of binary variables.

Collectives™ on Stack Overflow

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

4 Answers 4

3 Comments

Comments

Comments

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

1 Comment

Linked

Related