我正在实现等边双向分区算法的二进制表示,我想知道迭代具有相等(N/2)1 和 0 的 N 位的所有组合的最佳方法是什么。我试图找到最快的方法,而不是最容易编码的方法。谢谢。
问问题
635 次
1 回答
2
只是(N choose N/2)
; 您正在选择哪些位是 0,其余的是 1。
如果您有 10 位,并且想要 5 个零和 5 个 1,则有(10 choose 5) = 252
可能。
也可以看看:
正如已经指出的,这个数字是二项式系数(n k)
。什么时候k
是n/2
这个系数最大的时候;我相信你知道有很多可能性,这就是为什么你想要最快的算法来生成它们。
我不是对这个生成器进行微优化以使其尽可能快,而是首先用尽所有其他选项:你确定你不能比尝试所有可能性做得更好吗?这种蛮力解决方案无法扩展。
如果可能,请尝试找到更好的算法。
于 2010-04-14T05:09:53.820 回答