无需itertools与导入，纯Python实现0、1的n位全排列高效方案求助

需求说明 #

需要实现完全等价于list(product((0, 1), repeat=n))的功能：

• 不使用任何导入（包括itertools）
• 输出元素顺序与product完全一致（如n=3时输出[(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]）
• 性能优于现有的powerset_indices实现

已知字符串转换（如f'{i:0{n}b}'）和简单位运算遍历的方法效率低下，已被排除。

优化实现方案 #

基于原有的列表维护进位逻辑，优化进位时的批量重置操作（用Python底层实现的列表切片赋值替代Python级循环），减少循环内的开销：

from typing import Generator, Tuple

def optimized_binary_product(n: int) -> Generator[Tuple[int, ...], None, None]:
    if not isinstance(n, int) or n < 1:
        raise ValueError("The argument n must be a positive integer")

    current = [0] * n
    last_idx = n - 1
    total = 1 << n  # 等价于2^n

    for i in range(total):
        yield tuple(current)
        if i == total - 1:
            break  # 最后一次迭代无需进位

        # 从右向左找到第一个0的位置
        idx = last_idx
        while current[idx]:
            idx -= 1

        # 翻转该位置为1，批量重置右侧所有位为0
        current[idx] = 1
        if idx < last_idx:
            current[idx+1:] = [0] * (last_idx - idx)

性能对比测试 #

使用%timeit对各函数进行测试（测试环境：Python 3.10，n=16）：

from itertools import product

# 原实现
%timeit list(powerset_indices(16))
# 19.8 ms ± 92.2 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

# 优化后的实现
%timeit list(optimized_binary_product(16))
# 14.2 ms ± 45.1 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

# itertools.product基准
%timeit list(product((0, 1), repeat=16))
# 6.86 ms ± 32.5 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

优化后的实现相比原powerset_indices性能提升约28%，虽然仍慢于C实现的itertools.product，但已是纯Python环境下的高效方案。

原理说明 #

1. 状态维护：用列表current跟踪当前的二进制序列，避免每次重新生成序列的开销
2. 进位优化：从右向左找到第一个可翻转的0位，将其设为1后，通过列表切片赋值批量重置右侧所有位为0——切片赋值由Python底层C代码实现，比Python级循环快得多
3. 边界处理：最后一次迭代无需执行进位逻辑，减少不必要的计算

内容的提问来源于stack exchange，提问作者Ξένη Γήινος