如何快速生成含X个1的N长度所有元组

我想要编写一个Python函数，生成所有长度为N且恰好包含X个“1”的元组。例如，当需要生成长度为4且恰好含2个1的所有元组时，输出应为(1,1,0,0)、(1,0,1,0)、(1,0,0,1)、(0,1,1,0)、(0,1,0,1)和(0,0,1,1)。

最直观的方法是先生成所有N长度元组，再筛选出sum(tuple)≠X的元组，示例代码如下：

def all_tuples(length, x):
  output = [0 for y in range(length)]
  while not all(output): #yield states until all bits are 1s
    if(sum(output) == x):
      yield tuple(output)
    #now, increment the "output" as if it was binary
    for x in range(length):
      if(output[x]):
        output[x] = 0
      else:
        output[x] = 1
        break

但当N约为40时，这种暴力遍历所有元组的方法完全不可行，请问是否存在复杂度低于O(2^N)的实现方式？

当然存在。暴力法的问题在于遍历了所有2^{N种可能，而我们真正需要的只是其中C(N,X)个符合条件的元组（组合数，即从N个位置中选X个放1的组合数），所以最优解法的复杂度是O(C(N,X)*N)，远低于O(2}N)。

方法一：使用itertools.combinations（推荐） #

Python标准库的itertools.combinations可以高效生成所有位置组合，我们只需要根据这些组合构造元组即可：

import itertools

def generate_tuples(n, x):
    # 生成所有选X个位置的组合
    for positions in itertools.combinations(range(n), x):
        tuple_list = [0] * n
        for pos in positions:
            tuple_list[pos] = 1
        yield tuple(tuple_list)

这个方法利用了库的底层优化，代码简洁且效率极高。比如N=40、X=20时，直接生成所有C(40,20)个元组，无需遍历无关的可能性。

方法二：手动实现组合生成（无需依赖库） #

如果不想使用标准库，可以手动实现组合生成算法，核心是迭代生成所有X个位置的合法组合：

def generate_tuples_manual(n, x):
    # 初始化第一个组合：前X个位置为1
    positions = list(range(x))
    while True:
        # 构造当前元组
        tuple_list = [0] * n
        for pos in positions:
            tuple_list[pos] = 1
        yield tuple(tuple_list)
        
        # 寻找下一个组合
        i = x - 1
        # 从后往前找第一个可以递增的位置
        while i >= 0 and positions[i] == n - x + i:
            i -= 1
        if i < 0:
            break  # 所有组合已生成
        positions[i] += 1
        # 更新后续位置为连续递增的值
        for j in range(i + 1, x):
            positions[j] = positions[j-1] + 1

这个算法通过迭代更新位置组合，避免了无效遍历，效率和itertools实现接近，适合需要自定义逻辑的场景。

为什么这些方法更高效？ #

暴力法需要遍历2^{N个可能的元组，其中大部分会被过滤掉；而上述方法直接生成符合要求的元组，只处理C(N,X)个必要的情况。当N=40时，即使X=20，C(40,20)约为1.3×10}11，这是必须输出的结果数量，无法再优化，但比2^{40（约1×10}12）小一个数量级，节省了大量不必要的计算。

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