如何获得具有约束的数字列表的所有排列?

问题描述 投票:1回答: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])。

我该怎么做?

python
1个回答
4
投票

由于第一个列表元素始终为0,所以每个剩余元素都有两个选择;它应该等于前一个元素,还是更高?给出2 ^ 14种不同的组合。

[要生成它们,我们可以取(0, 1)的14个副本的乘积,并使用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)
© www.soinside.com 2019 - 2024. All rights reserved.