How to find all Boolean permutations of length n

[twsouthwick]

I need to create a routine that finds all Boolean permutations of length n. Say n=2, the algorithm needs to output

[0,0]
[1,0]
[0,1]
[1,1]

So far, I've tried the following code. I got this code from here, and tweaked it, but it gets a lot of repeats. So, if anyone knows a better way to do this (I know there is a permutation routine in the std algorithm), or can see the problem, that would be great!

#include <stdio.h>

void print(const int *v, const int size)
{
	if (v != 0) {static int count = 0;
	count++;
	printf("%2d | ",count);
	for (int i = 0; i < size; i++) {
		printf("%4d", v[i] );
	}
	printf("\n");
	}
}

void visit(int *Value, int N, int k)
{
	if(k != -1) Value[k] = 1;

	print(Value, N);

	for (int i = 0; i < N; i++)
		if (Value[i] == 0)
			visit(Value, N, i);

	if(k != -1) Value[k] = 0;
}

int vv[3];

int main(){
	const int N = 3;
	for (int i = 0; i < N; i++) {
		vv[i] = 0;
	}
	visit(vv, N, -1);
}

The output for this, if N=2 is:

 1 |    0   0
 2 |    1   0
 3 |    1   1
 4 |    0   1
 5 |    1   1

With N=2, there is only one extra value, but this gets larger very quickly. With N=3, the output becomes:

 1 |    0   0   0
 2 |    1   0   0
 3 |    1   1   0
 4 |    1   1   1
 5 |    1   0   1
 6 |    1   1   1
 7 |    0   1   0
 8 |    1   1   0
 9 |    1   1   1
10 |    0   1   1
11 |    1   1   1
12 |    0   0   1
13 |    1   0   1
14 |    1   1   1
15 |    0   1   1
16 |    1   1   1

Thanks for any help!

[helios]

Those are combinations, not permutations.

This is just a conversion to binary. It involves a combination of division and modulo, or shifting and ANDing.

[Disch]

ugh... recursion. Do you need to use recursion for this assignment or something? Generally you should try to avoid recursion wherever possible.

Anyway there's a very simple trick to this if you know about binary operators.. specifically AND (&) and bitshifting (<<, >>).

The trick is that the computer uses a binary numbering system internally... so it does all these binary permutations in normal counting. IE:

The number in decimal    How the computer stores it internally

_________________________________________
                    0    000
                    1    001
                    2    010
                    3    011
                    4    100
                  ...
                    7    111

You can take advantage of this by using the & operator to look at a specific bit:

int foo = 5;
if(foo & 1)  // examines the lowest bit
{
  // this code runs if the low bit == 1
}
else
{
  // this code runs if the low bit == 0
}

// example:
//          *  <- t
//   1 = 0001  <- rightmost bit is the low bit
// & 5 = 0101  <- 5 has the low bit set
// __________
//       0001  <- therefore the result is 1 

Bitshifting shift all of the bits right or left. Example:

int var = 12;  // 12 == 1100 in binary
var >>= 1;  // shift all bits to the right one
    // now var == 0110   (ie:  6) 

With those two tricks you should be able to find all binary permutations easily.


EDIT: doh, helios slipped in with a quickie.

[manojr]

This a strip down version of my program which can give any permutation and combination. I have modified a bit for your requirements. variable size if your N.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int temparr[]={0,1};
//int size = sizeof(temparr)/sizeof(*temparr);
int size=3;
vector<int> ArrSet(temparr,temparr + size);
const int choice=2; /*Only two choice, whether the
    current element is included in subset or not*/

int number_of_solutions=0;
string str(size,'0');

void print()
{
  //cout<<"{";
  cout << "[";
  for(int i=0;i<size;i++)
    {
      //if(str.at(i) == '0')
      //    cout<<ArrSet.at(i)<<" ";
      cout << str.at(i) << ",";
    }
    //cout<<"} ";
  cout <<"]\n";
};

void perm(int n)
{
    if(n == size)
    {
        number_of_solutions++;
        print();
        return;
    }
    for(int i = 0; i<choice;i++)
    {
        str.at(n)= '0' + i;
        perm(n+1);
    }
};

int main()
{
    perm(0);
    cout << "\nNumber of solutions " <<number_of_solutions <<endl;
    return 0;
}

[Disch]

ugh... why does everyone jump to recursion?

Also, wtf @ posting full solutions. Don't do his homework for him.

[jelllove]

#include <iostream>
#include <cmath>
using namespace std;


void PrintAll(int n = 2)
{
	if (n <= 0)
	{
		return;
	}

	//if n = 2, nTemp = 3
	//if n = 3, nTemp = 7
	//if n = 4, nTemp = 15
	//.... 

	int nTemp = (int)pow(2, n) - 1;

	for (int i = 0; i <= nTemp; i++)
	{
		cout<<"[";
		for (int k = 0; k < n; k++)
		{
			if ((i >> k) & 0x1)
			{
				cout<<"1";
			}
			else
			{
				cout<<"0";
			}

			if (k != n - 1)
			{
				cout<<",";
			}
		}

		cout<<"]"<<endl;
	}
}

hope it will help to you!

:)

[jelllove]

int main(int, char *[])
{
	PrintAll(3);
	return 0;
}

[twsouthwick]

Thanks for the help! Btw - this is not a homework assignment. It's part of a project I'm developing and couldn't figure out how to do it. I think I got it now!