Loop through every possible combination of values in a BitArray

Question

I'm trying to solve a larger problem. As part of this, I have created a BitArray to represent a series of binary decisions taken sequentially. I know that all valid decision series will have half of all decisions true, and half of all false, but I don't know the order:

 ttttffff
[||||||||]

Or:

 tftftftf
[||||||||]

Or:

 ttffttff
[||||||||]

Or any other combination where half of all bits are true, and half false.

My BitArray is quite a bit longer than this, and I need to move through each set of possible decisions (each possible combination of half true, half false), making further checks on their validity. I'm struggling to conceptually work out how to do this with a loop, however. It seems like it should be simple, but my brain is failing me.

EDIT: Because the BitArray wasn't massive, I used usr's suggestion and implemented a bitshift loop. Based on some of the comments and answers, I re-googled the problem with the key-word "permutations" and found this Stack Overflow question which is very similar.

Answer 1

I'd do this using a recursive algorithm. Each level sets the next bit. You keep track of how many zeroes and ones have been decided already. If one of those counters goes above N / 2 you abort the branch and backtrack. This should give quite good performance because it will tend to cut off infeasible branches quickly. For example, after setting tttt only f choices are viable.

A simpler, less well-performing, version would be to just loop through all possible N-bit integers using a for loop and discarding the ones that do not fulfill the condition. This is easy to implement for up to 63 bits. Just have a for loop from 0 to 1 << 63. Clearly, with high bitcounts this is too slow.

You are looking for all permutations of N / 2 zeroes and N / 2 ones. There are algorithms for generating those. If you can find one implemented this should give the best possible performance. I believe those algorithms use clever math tricks to only visit viable combinations.

Answer 2

If you're OK with using the bits in an integer instead of a BitArray, this is a general solution to generate all patterns with some constant number of bits set.

Start with the lowest valid value, which is with all the ones at the right side of the number, which you can calculate as low = ~(-1 << k) (doesn't work for k=32, but that's not an issue in this case).

Then take Gosper's Hack (also shown in this answer), which is a way to generate the next highest integer with equally many bits set, and keep applying it until you reach the highest valid value, low << k in this case.