Counting through all binary numbers with equal 1's and 0's

Question

I'm implementing a binary representation of an equal-side bi-partitioning algorithm and I'm wondering what the best way to iterate through all combinations of N bits that have equal (N/2) 1's and 0's. I'm trying to find the quickest way, not the easiest to code. Thanks.

Answer 1

It's just (N choose N/2); you're choosing which bits are 0s, the rest are 1s.

If you have 10 bits, and you want 5 zeroes and 5 ones, there are (10 choose 5) = 252 possibilities.

---

See also:

• Algorithm to return all combinations of k elements from n

---

As has been pointed out, this number is the binomial coefficient (n k). When k is n/2 is when this coefficient is the largest; I'm sure you're aware that there are numerous possibilities, which is why you wanted the fastest algorithm to generate them.

Instead of micro-optimizing this generator to make it the fastest possible, I'd first exhaust all other options: are you sure you can't do any better than trying all possibilities? This brute force solution does not scale.

Try to find a better algorithm if at all possible.