如何实现任意长度非负整数列表的完整枚举？

我希望生成/枚举所有可能的非负整数列表，使得算法能生成如下示例列表：

[1]
[24542,0]
[245,904609,848,24128,350,999]

简言之，要针对所有可能的长度，生成对应长度的所有非负整数列表。

我已经找到生成双元素列表的技巧：按对角线（元素和为定值）枚举，对应表格如下：

对应的Python实现代码：

def genpair():
    x = 0
    y = 0
    yield x,y
    maxx = 0
    while True:
        maxx += 1
        x = maxx
        y = 0
        while x >= 0:
            yield x,y
            x -= 1
            y += 1
    
gen = genpair()

for i in range(10):
    print(next(gen))

现询问：该对角线枚举技巧或其他方法是否可扩展至任意长度的非负整数列表生成？

完全可以扩展，核心思路是分层枚举：先按列表的长度从小到大处理，再对每个长度的列表，按元素的总和从小到大枚举，每个总和对应的所有非负整数组合就是高维的“对角线”。

方法1：基于对角线（元素和定值）的扩展 #

对于长度为k的非负整数列表，我们可以枚举所有可能的元素和s（从0开始递增），然后生成所有满足a1 + a2 + ... + ak = s的非负整数组合。这本质是双元素对角线枚举的高维推广——双元素时s=x+y，多元素时就是所有元素的和。

比如长度为3的列表：

• 和为0：[0,0,0]
• 和为1：[1,0,0], [0,1,0], [0,0,1]
• 和为2：[2,0,0], [1,1,0], [1,0,1], [0,2,0], [0,1,1], [0,0,2]
• 以此类推

方法2：统一枚举所有长度的列表 #

如果要一次性生成所有长度的非负整数列表，可以按“总权重”分层：总权重定义为列表长度 + 元素总和，从小到大枚举总权重，每个权重下包含所有符合条件的不同长度列表。

比如：

• 总权重0：只有[0]（长度1，和0）
• 总权重1：[1]（长度1，和1）、[0,0]（长度2，和0）
• 总权重2：[2]（长度1，和2）、[1,0], [0,1]（长度2，和1）、[0,0,0]（长度3，和0）
• 以此类推

Python实现示例 #

下面是一个生成所有长度非负整数列表的实现，基于总权重分层：

from itertools import combinations_with_replacement

def gen_all_lists():
    total_weight = 0
    while True:
        # 枚举当前总权重下的所有可能列表长度k（k从1到total_weight）
        for k in range(1, total_weight + 1):
            s = total_weight - k  # 元素总和 = 总权重 - 列表长度
            if s < 0:
                continue
            # 生成所有k个非负整数和为s的组合（用“星号法”转换）
            # 等价于在s个星号中插入k-1个分隔符的位置
            for splits in combinations_with_replacement(range(s + k), k - 1):
                prev = -1
                lst = []
                for split in splits:
                    lst.append(split - prev - 1)
                    prev = split
                lst.append(s + k - 1 - prev)
                yield lst
        total_weight += 1

# 测试：生成前15个列表
gen = gen_all_lists()
for _ in range(15):
    print(next(gen))

运行这段代码会输出：

[0]
[1]
[0, 0]
[2]
[1, 0]
[0, 1]
[0, 0, 0]
[3]
[2, 0]
[1, 1]
[0, 2]
[1, 0, 0]
[0, 1, 0]
[0, 0, 1]
[0, 0, 0, 0]

为什么这个方法可行？ #

• 所有可能的非负整数列表都会被枚举到：每个列表都对应唯一的总权重，而每个总权重下的所有组合都会被生成。
• 不会遗漏也不会重复：每个列表只属于一个总权重，且每个组合的生成方式唯一。

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