python之如何生成最大步长为 1 的所有非递减序列

我正在尝试获取具有特定约束的数字 0-14 的所有可能组合的列表。我不太确定如何表达这个所以让我解释一下。

• 每个列表的长度为 15。
• 第一个列表将是 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]。
• 每个列表中每个索引处的值不能超过索引本身，可以与前一个数字相同，也可以比前一个数字大。
• 最终列表将是 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]。

我正在寻找一个列表列表，其中包含具有这些约束的所有可能序列(例如，一个可能的序列是 [0, 1, 1, 2, 2, 3, 4, 5, 6, 6 , 7, 7, 7, 8, 8])。

我该怎么做？

请您参考如下方法:

由于第一个列表元素始终为 0，因此对于每个剩余元素，我们有两个选择；它应该等于前一个元素，还是更高？这给出了 2^14 种不同的组合。

要生成它们，我们可以取 14 个 (0, 1) 副本的乘积，并使用 itertools.accumulate 将每个副本转换为它们的部分和序列。 :

import itertools 
 
def solution(n): 
    for p in itertools.product((0, 1), repeat=n): 
        yield (0,) + tuple(itertools.accumulate(p)) 

例子:

>>> for p in solution(3): 
...     print(p) 
...  
(0, 0, 0, 0) 
(0, 0, 0, 1) 
(0, 0, 1, 1) 
(0, 0, 1, 2) 
(0, 1, 1, 1) 
(0, 1, 1, 2) 
(0, 1, 2, 2) 
(0, 1, 2, 3)