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