4

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.

Stuart
  • 1,733
  • 4
  • 21
  • 34

1 Answers1

2

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:

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.

Community
  • 1
  • 1
polygenelubricants
  • 376,812
  • 128
  • 561
  • 623
  • Interesting. Is that choose function what they call a binomial coeffecient? i.e. http://en.wikipedia.org/wiki/Binomial_coefficient – hookenz Apr 14 '10 at 05:12
  • Yes, I believe "n choose k" is how you casually say it in English, and it's also how Google calculator does it (just type in "`10 choose 5`"). It is the binomial coefficient, which of course appears in a lot of places (e.g. Pascal's triangle, etc). – polygenelubricants Apr 14 '10 at 05:15
  • Just be aware that on some architecture (e.g. Intel) recursive implementations can sometimes be faster (!) than their iterative equivalents. Implement both and measure. – vladr Apr 14 '10 at 05:18