英文:
Generating binary numbers with constraints
问题
生成一个Python或其他语言的脚本，返回符合以下约束的每个32位二进制数：考虑到每个二进制数中的1和0的模式，每个二进制数最多只能有一种情况，其中零的模式至少不重复一次。因此，如果我们在较小的7位二进制上进行练习，1010011是无效的（0和00是唯一的），但1010100是有效的（0出现两次，00出现一次），1010101是有效的（0出现3次）。最后，应将这些数字视为环，因此尾部的零和开头的零被视为一组（例如，0010包含集合000）。
我在这方面遇到困难，因为我的正常方法是使用蛮力...生成所有二进制数的列表，然后将每个数字都受到约束的限制。然而，有43亿个32位组合，使我的常规方法变得太慢。
英文:
Help me generate a script in python or another language that returns every 32 bit binary number meeting the following constraint: considering the patterns of 1’s and 0’s inherent in each binary number, there may be a maximum of one case per binary number where the pattern of zeroes does not repeat at least once. So if we were doing the exercise on smaller 7 bit binary, 1010011 is not valid (0, and 00 are unique), but 1010100 is valid (0 is found twice, 00 once) and 1010101 is valid (0 is found 3 times). Finally, these numbers should be thought of as rings, such that trailing zeroes and zeroes at the beginning are considered one group (eg 0010 contains the set 000).
I am struggling with this because my normal approach would be to use brute force… generate a list of all binaries and then subject each number to the constraint. However there are 4.3 billion 32 bit combinations, making my usual approach too slow.
答案1
得分: 2
我找不到一个足够快的32位解决方案，但我有一个比蛮力法稍好一些的东西：
这种方法将问题分成了几层，允许尽早排除不会产生有效比特集的模式。
一组连续的零由两边的1限定。而且，由于二进制数被视为一个"环"，我们可以将每个组视为一个"1"，后面跟着一系列连续的零（包括没有零的情况）。
这意味着32位将被分成具有总长度为32的组。因此，起点可以是32的部分（组）的[分区][1]，这些部分相加等于32。
在这些分区中，我们将排除具有多个非重复组大小（除了大小为1的情况，即不跟随任何"0"的"1"）的分区。这允许我们在执行任何排列或旋转之前排除组模式。
一旦我们获得了分区大小的组合，我们仍然需要找到这些组大小的不同排列，以将它们转换为比特模式。
最后，因为我们将组定义为以"1"开头，所以我们会错过一些比特模式，其中一系列零绕过32位二进制位列表的边界。这将需要执行一些旋转来获取完整的结果。
这是一个用于生成给定大小的分区的函数：
def partition(N, size):
if size == 1:
yield (N,) # 基本情况，只有1部分
return
for a in range(N // size + 1): # 更小的部分后面跟着
for p in partition(N - a * size, size - 1): # 相等或更大的部分
yield (a, *(n + a for n in p)) # 仅对增量进行递归
我们在一个生成器中使用这些分区，通过过滤掉具有多个非重复组大小（除了零大小组）的分区来产生有效的组合。partition() 函数生成0到N之间的条目，对应于每个组中的0的数量。这就是为什么将总值作为size-count给出，以排除1的数量的计算。
from collections import Counter
def genGroups(size=32):
for count in range(1, size):
for group in partition(size - count, count):
partCounts = Counter(group)
if sum(n and c == 1 for n, c in partCounts.items()) > 1:
continue
yield group
一旦我们获得了有效的组合，我们仍然需要找到这些组大小的不同排列：
def permuteDistinct(A):
if len(A) == 1:
yield tuple(A) # 单个值
return
used = set() # 跟踪起始值
for i, n in enumerate(A): # 对于每个起始值
if n in used:
continue # 尚未使用
used.add(n)
for p in permuteDistinct(A[:i] + A[i + 1:]):
yield (n, *p) # 起始值和其余部分
genBits() 函数将这些生成器组合起来，以获取组并将它们转换为比特模式。然后，它对它们进行旋转，以获取绕过二进制位列表的变体。
def genBits(size=32):
yield "0" * size # 边缘情况
seen = set()
for grouping in genGroups(size): #
for order in permuteDistinct(grouping):
bits = "".join("1" + "0" * n for n in order)
yield bits
i = bits.index("0")
bits = bits[i:] + bits[:i]
if bits in seen:
continue
seen.add(bits)
while bits.startswith("0"):
yield bits
bits = bits[1:] + bits[:1]
yield "1" * size # 边缘情况
输出：
for bits in genBits(5):
print(bits)
00000
10000
00001
00010
00100
01000
11000
00011
00110
01100
10001
11100
00111
01110
11001
10011
11010
01011
10110
01101
10101
11110
01111
11101
11011
10111
11111
性能：
from time import time
start = time()
count = sum(1 for _ in genBits(24)) # 8,949,112 个比特模式
print(count, time() - start) # 35 秒
# 其他大小 / 时间
genBits(22) # 2,213,116 个比特模式，在10秒内完成
genBits(25) # 17,938,807 个比特模式，在77秒内完成
genBits(27) # 71,767,133 个比特模式，在323秒内完成
genBits(29) # 286,383,035 个比特模式，在21分钟内完成
genBits(32) # 大约需要3小时才能生成20亿个模式
时间（和解决方案数量）呈指数增长。我没有耐心等待32位结果。
为了检查结果，我编写了一个比特模式验证函数，我在一个蛮力解决方案中使用了它：
from collections import Counter
from itertools import groupby
def isvalid(bits):
p = bits.find("1")
if p < 0:
return True # 所有零
bits = bits[p:] + bits[:p] # 旋转以从1开始
counts = Counter(len(g) for bit, (*g,) in groupby(bits) if bit == "0")
return sum(c == 1 for c in counts.values()) < 2
<details>
<summary>英文:</summary>
I couldn't find a fast enough solution for 32 bits but I have something that's a bit better than brute force:
The approach breaks down the problem in layers that allow early exclusion of patterns that won't produce a valid set of bits.
A group of consecutive zeros is delimited by 1s on each side. And, since the binary number is treated as a "ring", we can view each group as a "1" followed by a number of consecutive zeros (including no zeros at all).
This means that the 32 bits will be divided in groups with a total length of 32. Thus, the starting point can be the [partitioning][1] of 32 into parts (groups) that add up to 32.
Of these partitions, we would excludes the ones that have more than one occurrence of a non-repeated group size (other than a size of one which is a "1" not followed by any "0"). This allows us to exclude group patterns before any permutation or rotation is performed.
Once we obtain the combinations of partition sizes, we still need to find the distinct permutations of these group sizes to convert them into bit patterns.
Finally, because we defined the groups as starting with "1", we are missing the bit patterns where a sequence of zeros wraps around the boundaries of the 32 bits. This will require performing a few rotations get a complete result.
Here is a function to generate partitions of a given size for a number N:
def partition(N,size):
if size == 1 :
yield (N,) # base case, only 1 part
return
for a in range(N//size+1): # smaller part followed by
for p in partition(N-a*size,size-1): # equal or larger ones
yield (a, *(n+a for n in p)) # recursing on delta only
We use the partitions in a generator that will produce valid group combinations by filtering out the partitions that have more than one non-repeating group size (except zero-size groups). The partition() function produces entries in the range 0...N which corresponds to the number of 0s in each group. This is why it is given size-count as the total value in order to exclude the number of 1s from the computation.
from collections import Counter
def genGroups(size=32):
for count in range(1,size):
for group in partition(size-count,count):
partCounts = Counter(group)
if sum(n and c==1 for n,c in partCounts.items())>1:
continue
yield group
Once we get the valid group combinations, we still need to find the distinct permutations of these group sizes:
def permuteDistinct(A):
if len(A) == 1:
yield tuple(A) # single value
return
used = set() # track starting value
for i,n in enumerate(A): # for each starting value
if n in used: continue # not yet used
used.add(n)
for p in permuteDistinct(A[:i]+A[i+1:]):
yield (n,*p) # starting value & rest
The genBits() function combines these generators to obtain the groups and convert them into bit patterns. It then rotates them to get the variants that wrap around the binary bit list.
def genBits(size=32):
yield "0"*size # edge case
seen = set()
for grouping in genGroups(size): #
for order in permuteDistinct(grouping):
bits = "".join("1"+"0"*n for n in order)
yield bits
i = bits.index("0")
bits = bits[i:]+bits[:i]
if bits in seen: continue
seen.add(bits)
while bits.startswith("0"):
yield bits
bits = bits[1:]+bits[:1]
yield "1"*size # edge case
output:
for bits in genBits(5):
print(bits)
00000
10000
00001
00010
00100
01000
11000
00011
00110
01100
10001
11100
00111
01110
11001
10011
11010
01011
10110
01101
10101
11110
01111
11101
11011
10111
11111
performance:
from time import time
start = time()
count = sum(1 for _ in genBits(24)) # 8,949,112 bit patterns
print(count, time()-start) # 35 seconds
# other sizes / times
genBits(22) # 2,213,116 in 10 seconds
genBits(25) # 17,938,807 in 77 seconds
genBits(27) # 71,767,133 in 323 seconds
genBits(29) # 286,383,035 in 21 minutes
genBits(32) # should give 2 billion patterns in roughly 3 hours
The time (and number of solutions) grows exponentially. I wasn't patient enough to wait for the 32 bit result.
In order to check the result, i wrote a bit pattern validation function that I used in a brute force solution:
from collections import Counter
from itertools import groupby
def isvalid(bits):
p = bits.find("1")
if p<0: return True # all zeros
bits = bits[p:]+bits[:p] # rotate to start on a 1
counts = Counter(len(g) for bit,(*g,) in groupby(bits) if bit=="0")
return sum(c==1 for c in counts.values()) < 2
N = 20
sum(isvalid(f"{n:0{N}b}") for n in range(1<<N)) # 543,876 : 9 secs
sum(1 for _ in genBits(N)) # 543,876 : 2 secs
[1]: https://en.wikipedia.org/wiki/Partition_(number_theory)
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论