How to find all Boolean permutations of length n

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!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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!
Those are combinations, not permutations.

This is just a conversion to binary. It involves a combination of division and modulo, or shifting and ANDing.
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:

1
2
3
4
5
6
7
8
9
10
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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:

1
2
3
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.
Last edited on
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#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;
}

ugh... why does everyone jump to recursion?

Also, wtf @ posting full solutions. Don't do his homework for him.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#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!

:)
1
2
3
4
5
int main(int, char *[])
{
	PrintAll(3);
	return 0;
}
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!
Topic archived. No new replies allowed.