计算所有 1 和 0 相等的二进制数
我正在实现等边双分区算法的二进制表示，我想知道迭代具有相等 (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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
只是
（N选N/2）；你要选择哪些位是 0，其余的是 1。如果您有 10 位，并且需要 5 个零和 5 个一，则有
（10选5）= 252种可能性。另请参阅：
正如已经指出的，这个数字是二项式系数
(nk)。当k为n/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) = 252possibilities.See also:
As has been pointed out, this number is the binomial coefficient
(n k). Whenkisn/2is 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.