python - 如何生成最大步长为 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)