我想知道最有效的方法来生成每个给定长度的二进制数,其中有偶数个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 and 2 + 3
comb2 = 1010 # 1 + 3 and 2 + 4
comb3 = 1100 # 1 + 2 and 3 + 4
非常感谢。
编辑:
很抱歉之前没有提到这一点,但我不需要生成解的逆,所以我只需要一半的潜在排列。例如,在上面的例子中,我有1001
,1010
和1100
,但没有0110
,0101
或0011
。
编辑2:
最好的解决方案是由Mark提供的。为了只生成一半的二进制数(因为我不需要求逆),我使用下面的函数。我还将二进制数存储为整数,而不是字符串,并使用this answer中提供的方法将整数的位用作索引。
def binary_options(digits):
target = digits / 2
return [i for i in range(int('1' * (digits - 1), 2)) if i.bit_count() == target]
3条答案
按热度按时间r8xiu3jd1#
如果使用Python 3.10+,则可以使用
int.bit_count()
:因此,对于4位数中的偶数个0和1:
或者简单地计算一下:
一个更快的计数选项是生成N位的组合,一次取N/2,这比上面针对24位数的
.bit_count()
求和快约4倍:时序比较:
itertools
解决方案,生成位模式和值。例如,下面的迭代20次与尝试所有64(26)号码:输出:
au9on6nz2#
这是我的解决方案。
回想一下组合学,跨越K个位置的N个元素的唯一排列的数量是这样的:
对于任何给定的长度为N的二进制串,其中0和1的数量相同的“偶数串”的数量可以类似地计算如下:
在Python中:
简单来说就是:
让我们通过在决策树的每次迭代中附加一个或1来实现这一点
更新实施情况
测试它(打印字符串及其十进制值)
xdyibdwo3#
您可以从以下数字开始:
1 + 0 * half + 1 *(half - 1),其中half =目标长度/ 2
然后将每个1从右半部分逐位移动到左半部分。
下面是我得到的代码:
这里 i 是已经移动到左侧的1的数量,j 是0的初始序列中的当前位置。
对不起,如果指数化是混乱的,但代码应该工作,似乎对我优化。