partitioning - 计算所有等于 1 和 0 的二进制数

Question

我正在实现等边双向分区算法的二进制表示，我想知道迭代具有相等（N/2）1 和 0 的 N 位的所有组合的最佳方法是什么。我试图找到最快的方法，而不是最容易编码的方法。谢谢。

Answer 1

只是(N choose N/2); 您正在选择哪些位是 0，其余的是 1。

如果您有 10 位，并且想要 5 个零和 5 个 1，则有(10 choose 5) = 252可能。

---

也可以看看：

• 从 n 返回 k 个元素的所有组合的算法

---

正如已经指出的，这个数字是二项式系数(n k)。什么时候k是n/2这个系数最大的时候；我相信你知道有很多可能性，这就是为什么你想要最快的算法来生成它们。

我不是对这个生成器进行微优化以使其尽可能快，而是首先用尽所有其他选项：你确定你不能比尝试所有可能性做得更好吗？这种蛮力解决方案无法扩展。

如果可能，请尝试找到更好的算法。