生成满足约束条件的32位环形二进制数的脚本开发需求

问题分析 #

首先明确约束核心：

• 环形二进制数：首尾相连，连续零段会合并（如开头和结尾都是0则合并为一个长零段）
• 零模式：连续0的长度（如单独0对应模式1，两个连续0对应模式2）
• 有效条件：所有零模式中，最多一种模式的出现次数小于2（即仅出现1次），其余模式出现次数≥2；无零模式（全1）或仅一种零模式（全0或单个零段）也满足条件。

暴力枚举2^32种组合完全不可行，因此采用构造法：基于环形结构的交替1段/零段特性，直接生成符合条件的段组合，再转换为二进制数。

实现思路 #

1. 边界情况处理：直接生成全1、全0两种二进制数。
2. 构造零段组合：
   • 情况1：所有零模式出现次数≥2（即每个连续0长度至少出现两次）
   • 情况2：恰好一种零模式仅出现1次，其余模式出现次数≥2
3. 构造对应1段组合：根据零段总长度，生成所有满足总和要求的正整数长度的1段组合（利用星号法生成正整数解）
4. 生成二进制字符串：将1段和零段交替拼接，分别生成以1段开头和以0段开头的两种字符串（环形结构下起始段不同对应不同32位二进制数）

Python代码实现 #

import itertools

def generate_zero_segments():
    # 情况1：所有零模式出现次数≥2
    for m in range(2, 17):  # m为零段/1段数量，最大16（m*1 + m*1 ≤32）
        max_sum = 32 - m
        if max_sum < m:
            continue
        # 枚举不同零模式的数量t，每个模式出现次数≥2
        for t in range(1, m//2 + 1):
            target = m - 2 * t
            if target < 0:
                continue
            # 用星号法拆分target为t个非负整数，对应c_i=2+d_i
            splits = itertools.combinations(range(target + t - 1), t - 1)
            for split in splits:
                prev = 0
                counts = []
                for s in split:
                    counts.append(2 + (s - prev))
                    prev = s + 1
                counts.append(2 + (target - (prev - (t - 1))))
                # 生成符合总和要求的零段长度组合
                def find_ks(index, current_k, current_sum):
                    if index == t:
                        if current_sum <= max_sum:
                            ks = []
                            for i in range(t):
                                ks.extend([current_k[i]] * counts[i])
                            yield ks
                        return
                    start = current_k[-1] + 1 if index > 0 else 1
                    remaining = max_sum - current_sum
                    min_remaining = start * counts[index]
                    if min_remaining > remaining:
                        return
                    max_k = remaining // counts[index]
                    for k in range(start, max_k + 1):
                        yield from find_ks(index + 1, current_k + [k], current_sum + k * counts[index])
                for ks in find_ks(0, [], 0):
                    yield (m, ks)
    # 情况2：恰好一种零模式仅出现1次，其余≥2次
    for m in range(1, 17):
        if m % 2 == 0:
            continue  # 1+2t=m → m必须为奇数
        max_sum = 32 - m
        if max_sum < m:
            continue
        t = (m - 1) // 2
        # m=1时，仅一个零段
        if t == 0:
            for k0 in range(1, 32):
                yield (m, [k0])
            continue
        # 生成t个不同的零模式（各出现2次）+1个单独的零模式
        for k_list in itertools.combinations(range(1, max_sum // 2 + 1), t):
            sum_ks = sum(k_list) * 2
            remaining = max_sum - sum_ks
            if remaining < 1:
                continue
            for k0 in range(1, remaining + 1):
                if k0 not in k_list:
                    ks = [k0]
                    for k in k_list:
                        ks.extend([k] * 2)
                    yield (m, ks)

def generate_one_segments(total_length, m):
    # 生成m个正整数，总和为total_length
    if total_length < m:
        return []
    splits = itertools.combinations(range(total_length - 1), m - 1)
    for split in splits:
        prev = 0
        segments = []
        for s in split:
            segments.append(s - prev + 1)
            prev = s + 1
        segments.append(total_length - prev)
        yield segments

def generate_valid_binary_numbers():
    # 输出边界情况
    yield '1' * 32
    yield '0' * 32
    # 生成非边界情况的二进制字符串
    for (m, ks) in generate_zero_segments():
        sum_ks = sum(ks)
        total_one = 32 - sum_ks
        for ls in generate_one_segments(total_one, m):
            # 以1段开头
            bits = []
            for l, k in zip(ls, ks):
                bits.append('1' * l)
                bits.append('0' * k)
            yield ''.join(bits)
            # 以0段开头
            bits = []
            for k, l in zip(ks, ls):
                bits.append('0' * k)
                bits.append('1' * l)
            yield ''.join(bits)

# 示例：输出前10个有效二进制数
if __name__ == '__main__':
    for idx, binary_str in enumerate(generate_valid_binary_numbers()):
        if idx >= 10:
            break
        print(f"{idx+1}: {binary_str} (decimal: {int(binary_str, 2)})")

代码说明 #

1. generate_zero_segments：生成所有符合约束的零段长度组合，分两种情况枚举，通过星号法和组合生成避免重复。
2. generate_one_segments：根据1段总长度和数量，生成所有可能的1段长度组合，确保每个1段长度≥1。
3. generate_valid_binary_numbers：拼接1段和零段生成二进制字符串，同时处理两种起始段情况，确保覆盖所有有效32位二进制数。

该方案通过组合构造替代暴力枚举，大幅降低计算量，可高效生成所有满足约束的32位二进制数。

内容的提问来源于stack exchange，提问作者Sir Roland Baggybottom IV