枚举所有可能的非负整数列表（任意长度）

Question

我想生成/枚举所有可能的非负整数列表，以便算法在某个时刻生成如下所示的列表

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

换句话说，对于所有可能的非负整数，生成包含那么多非负整数的所有可能的列表。

我发现包含两个数字的列表的技巧是像这样对角枚举它们的值

第一个值\第二个值	0	1	2	3
0	0（这将首先生成）	2（第三个等）	5	9
1	1（这一秒）	4	8
2	3	7
3	6

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))

但是同样的技巧（或其他技巧）是否也适用于任意长度的列表？

Answer 1

执行此操作的无数方法之一：

想象一条包含单元格 1、2、3 直至无穷大的数轴。现在考虑一个二进制数表示，其中的位指示单元格边界是否有“中断”。所以，

1  -> [1]
10 -> [2]
11 -> [1,1]
100 -> [3]
101 -> [2, 1]
110 -> [1, 2]

注意位数与列表的总和相同，正位数表示列表元素的数量。代码看起来有点像：

def list_gen(n):
    res = []
    counter = 0
    while n:
        counter += 1
        n, flag = divmod(n, 2)
        if flag:
            res.append(counter)
            counter = 0
    return res