C# simple permutation of a binary array

  • Thread starter Thread starter Rob
  • Start date Start date
R

Rob

I have a binary array {0,0,1,1,0,0,1,1}

How can I efficently permutate the array?
e.g.,
{0,0,0,1,1,0,1,1,0}.

........
 
Rob said:
I have a binary array {0,0,1,1,0,0,1,1}

How can I efficently permutate the array?
e.g.,
{0,0,0,1,1,0,1,1,0}.

.......
Click to expand...

That's not a permutation, you have eight bits in the original array and
nine bits in the example...

Supposing that you actually want to do permutations, you just have to
find the comnintations with the same number of bits set. That's more
efficient to do using numbers than arrays:


static int CountBits(int value) {
value <<= 1;
int cnt = 0;
while (value != 0) {
cnt += (0xe994 >> (value & 14)) & 3;
value >>= 3;
}
return cnt;
}

static IEnumerable<int> PermutateBits(int bits, int bitsSet) {
int min = 0x7fffffff >> (31 - bitsSet);
int max = min << (bits - bitsSet);
for (int i = min; i <= max; i++) {
if (CountBits(i) == bitsSet) {
yield return i;
}
}
}

static string Bin(int value, int len) {
return (len > 1 ? Bin(value >> 1, len - 1) : null) + "01"[value & 1];
}



Usage:

foreach (int i in PermutateBits(8, 4)) {
Console.WriteLine(Bin(i, 8));
}


Output:

00001111
00010111
00011011
00011101
00011110
00100111
00101011
00101101
00101110
00110011
00110101
00110110
00111001
00111010
00111100
01000111
01001011
01001101
01001110
01010011
01010101
01010110
01011001
01011010
01011100
01100011
01100101
01100110
01101001
01101010
01101100
01110001
01110010
01110100
01111000
10000111
10001011
10001101
10001110
10010011
10010101
10010110
10011001
10011010
10011100
10100011
10100101
10100110
10101001
10101010
10101100
10110001
10110010
10110100
10111000
11000011
11000101
11000110
11001001
11001010
11001100
11010001
11010010
11010100
11011000
11100001
11100010
11100100
11101000
11110000
 
I'm sorry if this is harsh but did you even try using Google? I just typed
in Permutations on Google and the first hit (wikipedia) has code examples.
 
I just have to interject: "permute," not "permutate."

It feels so good to know I am not the only obsessive compulsive disorder
around here :-)
 
Your interjectificationisationizing is noted. ;)
Click to expand...

Argh. In America, that's interjectificationiZationizing, buddy....

There's a commercial out right now for some beer where this guy is talking
very seriously. At one point he says something like "No destination is the
destination of the undestinated." It cracks me up every time. It reminds me
of the line from Zorro, the Gay Blade: "Let them know that HE is here, to
help the helpless, to befriend the friendless, and to defeat...the
defeatless!"

Language is fun.
 
Hi there,

How did you come up with the values:
0xe994
14
3

in the CountBits(int value) method.

They are hard coded and dont have any equation that can explain it.

If you can that would be excellent :)
 
david said:
Hi there,

How did you come up with the values:
0xe994
14
3

in the CountBits(int value) method.

They are hard coded and dont have any equation that can explain it.

If you can that would be excellent :)
Click to expand...

The value 0xe994 is just a bit mask:

11 01 10 01 10 01 01 00

Each two bits represent the number of bits in a three bit value. The
method chops the value up in three bit chunks and adds up the number of
bits in each chunk.

14 is 7 times 2, i.e. the three lower bits multiplied by 2 to get an
index to a pair of bits in the bit mask.
 
Back
Top