python-3.x 生成具有偶数0和1的给定长度的所有二进制数

tkclm6bt  于 2023-05-19  发布在  Python
关注(0)|答案(3)|浏览(201)

我想知道最有效的方法来生成每个给定长度的二进制数,其中有偶数个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

非常感谢。
编辑:
很抱歉之前没有提到这一点,但我不需要生成解的逆,所以我只需要一半的潜在排列。例如,在上面的例子中,我有100110101100,但没有011001010011
编辑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]
r8xiu3jd

r8xiu3jd1#

如果使用Python 3.10+,则可以使用int.bit_count()

>>> for i in range(16):
...   print(f'{i:04b}, count={i.bit_count()}')
...
0000, count=0
0001, count=1
0010, count=1
0011, count=2
0100, count=1
0101, count=2
0110, count=2
0111, count=3
1000, count=1
1001, count=2
1010, count=2
1011, count=3
1100, count=2
1101, count=3
1110, count=3
1111, count=4

因此,对于4位数中的偶数个0和1:

>>> for i in range(16):
...   if i.bit_count() == 2:
...     print(f'{i:04b}')
...
0011
0101
0110
1001
1010
1100

或者简单地计算一下:

>>> sum(1 for i in range(2**4) if i.bit_count() == 2)
6
>>> sum(1 for i in range(2**24) if i.bit_count() == 12)
2704156

一个更快的计数选项是生成N位的组合,一次取N/2,这比上面针对24位数的.bit_count()求和快约4倍:

>>> from itertools import combinations as C
>>> numbits = 24
>>> target = numbits // 2
>>> sum(1 for c in C(range(numbits), target))
2704156

时序比较:

C:\>py -m timeit -s "from itertools import combinations as C" "sum(1 for c in C(range(24), 12))"
1 loop, best of 5: 383 msec per loop

C:\>py -m timeit "sum(1 for i in range(2**24) if i.bit_count() == 12)"
1 loop, best of 5: 1.53 sec per loop

itertools解决方案,生成位模式和值。例如,下面的迭代20次与尝试所有64(26)号码:

from itertools import combinations as C
numbits = 6
target = numbits // 2
for c in C([1<<n for n in range(numbits)], target):
    value = sum(c)
    print(f'{value:0{numbits}b} {value}')

输出:

000111 7
001011 11
010011 19
100011 35
001101 13
010101 21
100101 37
011001 25
101001 41
110001 49
001110 14
010110 22
100110 38
011010 26
101010 42
110010 50
011100 28
101100 44
110100 52
111000 56
au9on6nz

au9on6nz2#

这是我的解决方案。
回想一下组合学,跨越K个位置的N个元素的唯一排列的数量是这样的:

P =     N!
    -----------
      P! (N-P)!

对于任何给定的长度为N的二进制串,其中0和1的数量相同的“偶数串”的数量可以类似地计算如下:

permutations =          N!
               ----------------
                 (N/2)! * (N/2)!

在Python中:

P = (math.factorial(N) // math.factorial(N//2)) // math.factorial(N//2)

简单来说就是:

P = math.comb(N, N//2)

让我们通过在决策树的每次迭代中附加一个或1来实现这一点

更新实施情况

import math

def getNumberForIteration(i, length, remaining):
    if (i < 0 or length < remaining or remaining < 0 or length < 0): raise "Error!"
    result = 0
    while (length > remaining) and (length > 0) and (remaining > 0):
        leftCombos = math.comb(length-1,remaining)
        if (i < leftCombos):
            result = result << 1         # append 0
        else:
            result = (result << 1) + 1   # append 1
            remaining = remaining - 1
            i = i - leftCombos
        length = length - 1
    while (remaining > 0):          # pad the end with 1's
        result = (result << 1) + 1   
        remaining = remaining - 1
        length = length - 1
    if (length > 0):                # pad the end with 0's
        result = result << length

    return result

def print_binary_numbers_with_half_the_bits_set(bitLength):
    iterations = math.comb(bitLength, bitLength//2)
    for i in range(0,iterations):
        val = getNumberForIteration(i, bitLength, bitLength//2)
        f = "{0:0" + str(bitLength) + "b}"
        s = f.format(val)
        print(i, s, val)

测试它(打印字符串及其十进制值)

>>> print_binary_numbers_with_half_the_bits_set(6)
000111 7
001011 11
001101 13
001110 14
010011 19
010101 21
010110 22
011001 25
011010 26
011100 28
100011 35
100101 37
100110 38
101001 41
101010 42
101100 44
110001 49
110010 50
110100 52
111000 56
xdyibdwo

xdyibdwo3#

您可以从以下数字开始:
1 + 0 * half + 1 *(half - 1),其中half =目标长度/ 2
然后将每个1从右半部分逐位移动到左半部分。
下面是我得到的代码:

def binary_even(length):
    half = int(length/2)
    result = 0

    for i in range(0, half - 1, 1):
        for j in range(half - i, -1, -1):
            num = int("1"*(i+1) + "0"*j + "1" + "0"*(half-j) + "1"*(half-2-i))
            # Your operations with the number
        
    return result

这里 i 是已经移动到左侧的1的数量,j 是0的初始序列中的当前位置。
对不起,如果指数化是混乱的,但代码应该工作,似乎对我优化。

相关问题