通过所有等于1和0的二进制数进行计数 [英] Counting through all binary numbers with equal 1's and 0's
问题描述
我正在实现等边双向分配算法的二进制表示，并且我想知道迭代（N / 2）1和0的N位的所有组合的最佳方法是什么。我正在尝试找到最快的方法，而不是最简单的编码。
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.
推荐答案
它只是（N选择N / 2）；您选择的位是0，其余的是1。
It's just (N choose N/2); you're choosing which bits are 0s, the rest are 1s.
如果您有10位，并且想要5个零和5个，则有 （10选择5）= 252 可能性。
If you have 10 bits, and you want 5 zeroes and 5 ones, there are (10 choose 5) = 252 possibilities.
- Algorithm to return all combinations of k elements from n
的k个元素数字是二项式系数（nk）。当 k 是 n / 2 时，该系数最大。我敢肯定，您知道存在很多可能性，这就是为什么您想要最快的算法来生成它们的原因。
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.
这篇关于通过所有等于1和0的二进制数进行计数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
