求高效生成指定长度、0和1数量相等的半数二进制数的方法
生成指定长度且0、1数量相等的二进制数的高效实现
我想找到生成指定长度且0和1数量相等的二进制数的最高效实现方式。目前我用的暴力法需要生成字符串,效率很低,代码如下:
def max_bits(b): return (1 << b) - 1 def binary_options(digits): target = digits / 2 return [f"{i:b}" for i in range(max_bits(digits - 1), 2 ** digits) if f"{i:b}".count("0") == target]
这些二进制数用来作为索引,将数组分成两个均等部分并计算所有可能组合的和,因此不需要存储组合,可以边生成边求和,也不需要二进制数的字符串形式。举个例子:
arr = [1,2,3,4] comb1 = 1001 # 对应分组求和:1+4 和 2+3 comb2 = 1010 # 对应分组求和:1+3 和 2+4 comb3 = 1100 # 对应分组求和:1+2 和 3+4
补充说明1
抱歉之前没提到,我不需要生成逆序的结果,只需要一半的可能排列。比如上面的例子里,我只需要1001、1010、1100,不需要0110、0101、0011。
补充说明2
最终采用了Mark提供的最优方案。为了只生成半数二进制数(避免逆序结果),我使用了以下函数,同时将二进制数以整数形式存储,而非字符串,利用整数的位来作为索引:
def binary_options(digits): target = digits / 2 return [i for i in range(int('1' * (digits - 1), 2)) if i.bit_count() == target]
内容的提问来源于stack exchange,提问作者am1234
相关产品推荐
相关产品推荐

