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.

What's the question? Are you asking how to tell if a byte array meets these conditions? How to generate it? Something else? — Paul Phillips, May 25 '14 at 20:11
I think one approach would be to [generate all permutations](http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations) of a list consisting of `n/2` zeros and `n/2` ones. — Blorgbeard, May 25 '14 at 20:13

score 2 · Accepted Answer · answered May 25 '14 at 20:11

2

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.

answered May 25 '14 at 20:11

usr

168,620
35
240
369

Thanks so much. Will quickly try it out. I can see how I can use this method to generate new BitArrays, each of which have half false, half true. Sorry if I'm being dim, but how would I move through the overall set of possible BitArrays without repeating any of the previous ones? How would I seed the recursive BitArray generator to get the "next" BitArray each time? It would probably help to mention that I'm trying to count the total number of valid decision series! – Orphid May 25 '14 at 20:23
1

You're just counting them? There's a simple formula for that. It's (N/2) over N. http://en.wikipedia.org/wiki/Binomial_coefficient – usr May 25 '14 at 21:27
Not just counting them, predictable/sequential movement through the overall series of possible BitArrays is important as well. Thanks for the link though! – Orphid May 25 '14 at 22:51
If you require incremental computation you might want to use the permutation idea. I know that the C++ standard library has a function for that so it is possible. We're exceeding my knowledge here. – usr May 25 '14 at 23:08

score 2 · Answer 2 · edited May 23 '17 at 12:31

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.

score 1 · Answer 3 · answered May 25 '14 at 20:55

This will result in duplicates, but you could check for duplicates before adding to the List if you want to.

  static void Main(string[] args)
  {
     // Set your bits here:
     bool[] bits = { true, true, false };
     BitArray original_bits = new BitArray(bits);

     permuteBits(original_bits, 0, original_bits.Length - 1);

     foreach (BitArray ba in permutations)
     {
        // You can check Validity Here
        foreach (bool i in ba)
        {
           Console.Write(Convert.ToInt32(i));
        }
        Console.WriteLine();
     }
  }

  static List<BitArray> permutations = new List<BitArray>();

  static void permuteBits(BitArray bits, int minIndex, int maxIndex)
  {
     int current_index;
     if (minIndex == maxIndex)
     {
        permutations.Add(new BitArray(bits));
     }
     else
     {
        for (current_index = minIndex; current_index <= maxIndex; current_index++)
        {
           swap(bits, minIndex, current_index);
           permuteBits(bits, minIndex + 1, maxIndex);
           swap(bits, minIndex, current_index);
        }
     }
  }

  private static void swap(BitArray bits, int i, int j)
  {
     bool temp = bits[i];
     bits[i] = bits[j];
     bits[j] = temp;
  }

score 0 · Answer 4 · answered May 25 '14 at 20:25

0

If you want to clear the concept of finding all the permutation of a string having duplicates entry(i.e zeros and ones), you can read this article

They have used recursive solution to solve this problem and the explanation is also good.

answered May 25 '14 at 20:25

Ranjit Singh

3,715
1
21
35

Loop through every possible combination of values in a BitArray

4 Answers4