Python中快速生成0到2**n-1数字集合的最优方法

首先必须明确：当n=30时，目标集合包含约10亿个元素，无法在常规内存中完整存储为Python集合（每个整数在集合中至少占用28字节，10亿个元素需要280GB以上内存）。因此需要根据你的实际需求选择对应方案：

1. 仅需计算集合大小（最快） #

无需生成任何数字，用动态规划计算不含三个连续1的数的数量，再用总数量2^n减去该值即可。

动态规划公式：

• dp[0] = 1（空数）
• dp[1] = 2（0、1）
• dp[2] = 4（00、01、10、11）
• dp[i] = dp[i-1] + dp[i-2] + dp[i-3]（最后一位为0时继承dp[i-1]；最后两位为10时继承dp[i-2]；最后三位为110时继承dp[i-3]，避免出现连续三个1）

代码实现：

def count_no_three_consecutive_ones(n):
    if n == 0:
        return 1
    elif n == 1:
        return 2
    elif n == 2:
        return 4
    a, b, c = 1, 2, 4
    for _ in range(3, n + 1):
        d = a + b + c
        a, b, c = b, c, d
    return c

n = 30
total = 2 ** n
valid_count = total - count_no_three_consecutive_ones(n)
print(f"符合条件的数字数量：{valid_count}")

该方法时间复杂度为O(n)，计算n=30仅需几微秒。

2. 需要遍历符合条件的数字（内存友好） #

用回溯生成器逐个生成符合条件的数，无需一次性存储全部元素，遍历过程中可直接处理每个数字。

代码实现：

def generate_three_consecutive_ones_gen(n):
    def backtrack(pos, current, has_three):
        if pos == n:
            if has_three:
                yield current
            return
        if has_three:
            # 已出现连续三个1，后续位可自由选择0/1
            yield from backtrack(pos + 1, current << 1, True)
            yield from backtrack(pos + 1, (current << 1) | 1, True)
        else:
            # 加0，不会产生连续三个1
            yield from backtrack(pos + 1, current << 1, False)
            # 加1，检查是否出现连续三个1
            new_current = (current << 1) | 1
            if (new_current & 0b111) == 0b111:
                yield from backtrack(pos + 1, new_current, True)
            else:
                yield from backtrack(pos + 1, new_current, False)
    
    yield from backtrack(0, 0, False)

# 遍历示例
for num in generate_three_consecutive_ones_gen(30):
    # 处理每个数字，比如写入文件或计算
    pass

该生成器直接构建符合条件的二进制数，避免遍历全量10亿个数，效率远高于原方法。

3. 为什么原方法速度极慢 #

当n=30时，{i for i in range(2**n)}需要生成10亿个整数并加入集合：

• 内存开销巨大：仅存储这些整数就需要数GB内存，集合的哈希表结构还会额外占用更多内存。
• 时间开销大：遍历10亿个数、计算哈希、处理哈希冲突的过程会消耗大量CPU资源，导致速度极慢。

内容的提问来源于stack exchange，提问作者Juan