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

Question

我正在尝试获取具有某些限制的数字 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]）。

我该怎么做？

Answer 1

由于第一个列表元素始终为 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)