python 没有 itertools 的带约束的组合器列表

Question

假设我有一个包含以下元素的列表 [a,b,c,d,e]

如何生成所有可能的组合，使每个值都可以向右、向左或在同一位置移动。例如，对于上面的列表，所有可能的必需组合都是

(a, b, c, d, e)
(a, b, c, e, d)
(a, b, d, c, e)
(a, c, b, d, e)
(a, c, b, e, d)
(b, a, c, d, e)
(b, a, c, e, d)
(b, a, d, c, e)

我能想到的一种方法是，找到所有排列，然后根据上述条件进行过滤，但是当列表大小为 15 时，itertools 将不起作用。知道如何为大列表执行此操作吗？

Answer 1

every value can be moved to right, left or at the same position

在您的示例中，这排除了第一项（只能向右移动）和最后一项（只能向左移动）。因此，天真地，你的五个项目中每一个的有效移动看起来像：

>>> moves = [(0, 1)] + [(-1, 0, 1)] * 3 + [(-1, 0)]
>>> moves
[(0, 1), (-1, 0, 1), (-1, 0, 1), (-1, 0, 1), (-1, 0)]

其中-1向左移动，0保持原位，1向右移动。一旦你有了这个，你可以使用 itertools.product 来生成这些动作的所有组合。

但是，你要求 5 个项目的 8 个输出，我得到：

>>> from itertools import product
>>> all_moves = list(product(*moves))
>>> len(all_moves)
108

所以看起来有些动作组需要重复（这是合乎逻辑的 - 例如 (0, -1, 0, 0, 0) 看起来就像 (1, 0, 0, 0, 0)）和一些可能实际上不能应用（你会如何解决(0, -1, -1, -1, -1)？）

>>> all_moves[:5]
[(0, -1, -1, -1, -1), (0, -1, -1, -1, 0), (0, -1, -1, 0, -1), (0, -1, -1, 0, 0), (0, -1, -1, 1, -1)]

因此，您的下一步是弄清楚如何将每个移动元组应用于您的起始列表 - 为此，您将必须知道如何解决冲突（如果第一项向前移动，第三项向前移动向后移动，例如 (1, 0, -1, 0, 0)，结果是什么？）这可能揭示了一种可以进一步简化问题的方法。

Answer 2

这是你想要的：

def swap_permute(vals):
    if len(vals) < 2:
        return [vals[:]]

    r1 = swap_permute(vals[1:])
    s1 = [vals[:1] + x for x in r1]

    r2 = swap_permute(vals[2:])
    s2 = [vals[1::-1] + x for x in r2]

    return s1 + s2

调用时：

swap_permute(["a", "b", "c", "d", "e"])

结果是：

[['a', 'b', 'c', 'd', 'e'],
 ['a', 'b', 'c', 'e', 'd'],
 ['a', 'b', 'd', 'c', 'e'],
 ['a', 'c', 'b', 'd', 'e'],
 ['a', 'c', 'b', 'e', 'd'],
 ['b', 'a', 'c', 'd', 'e'],
 ['b', 'a', 'c', 'e', 'd'],
 ['b', 'a', 'd', 'c', 'e']]

这与您发布的输出匹配，实际上顺序也匹配。

解决方案是基于观察，当vals至少有2个元素时，解决方案可以分为两种情况：

第一个元素在其原始位置的那些
交换前两个元素的那些

python 没有 itertools 的带约束的组合器列表

python combinators list with constraints without itertools

python

combinations

permutation

combinatorics