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]）。

我该怎么做呢？

标签： pythoncombinatorics

Answer 1

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

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

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)