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.
+2
A:
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.
polygenelubricants
2010-04-14 05:09:53
Interesting. Is that choose function what they call a binomial coeffecient? i.e. http://en.wikipedia.org/wiki/Binomial_coefficient
Matt H
2010-04-14 05:12:22
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
2010-04-14 05:15:23
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
2010-04-14 05:18:37