python - Python中固定前一个元素的排列

Question

所以我遇到了列表中固定前一个元素的排列问题。所以，我有列表，它是从 1 到 n 的有序数字序列。

编辑

这里是我的问题的重新表述:你能想象一个 TreeMap 吗？因此，第一级 - 它是顶部(也称为父)顶点。所以，如果我们有像 [1, 2, 3, 4] 这样的顶点，我们的下一步将是进行排列，将所有数字插入位置 n，这意味着在输出中我们会有这个:

1.1 级 [1, 2, 3, 4]

2.1 级 [1, 2, 4, 3]

3.1 级 [1, 3, 4, 2]

4.1 级 [2, 3, 4, 1]

所以，然后我们看第 1.1 层，对第 n-1 个元素进行排列(4 是固定的，不参与该层的排列)。输出将是:

1.1.1 等级 [1, 2, 3, 4]

1.1.2 等级 [1, 3, 2, 4]

1.1.3 等级 [2, 3, 1, 4]

我们采用了 1.1.1 lvl 并修复了 n-2 元素(如您所见，没有必要修复第一个元素)。所以，在这个层面上，我们固定了 3 和 4，即第 n-1 和 n元素，输出是:

1.1.1.1 lvl [1, 2, 3, 4]

1.1.1.2 lvl [2, 1, 3, 4]

我们在这里吃过饭，但还没吃完。继续升级(它是 1.1.2 级)。并排列它。这里我们固定了第 n-1 个元素(它是 2)和第 n 个(它是 4)

1.1.2.1 lvl [1, 3, 2, 4]

1.1.2.2 lvl [3, 1, 2, 4]

到此结束。转到上层。这里修复了1和4。所以，

1.1.3.1 lvl [2, 3, 1, 4]

1.1.3.2 lvl [3, 2, 1, 4]

我们已经完成了 1.1 级并进入 2.1 级，在那里我们重复相同的过程。

那么，问题是:如何在 python 中执行此操作？

Answer 1

通过交换两个元素，您的结果中的排列均不同于前一个元素。

交换两个元素对应于排列面体中的一条边。

这表明您正在尝试根据某些标准访问排列面体中的顶点。你能用几何术语解释一下标准是什么吗？

例如，一个可能的问题是如何通过在每一轮仅交换两个元素来生成所有可能的排列。这对应于在置换面体上找到哈密顿路径。 Steinhaus-Johnson-Trotter algorithm给出了这个问题的答案它给出了从给定位置找到下一个排列的 O(n) 方法。

编辑

这是更新问题的一些 Python 代码:

def perms(A):
    if len(A)==1:
        yield A
    for i in xrange(len(A)-1,-1,-1):
        for B in perms(A[:i]+A[i+1:]):
            yield B+A[i:i+1]

运行

for a in perms([1,2,3,4]):
    print a

打印以下内容:

[1, 2, 3, 4]
[2, 1, 3, 4]
[1, 3, 2, 4]
[3, 1, 2, 4]
[2, 3, 1, 4]
[3, 2, 1, 4]
[1, 2, 4, 3]
[2, 1, 4, 3]
[1, 4, 2, 3]
[4, 1, 2, 3]
[2, 4, 1, 3]
[4, 2, 1, 3]
[1, 3, 4, 2]
[3, 1, 4, 2]
[1, 4, 3, 2]
[4, 1, 3, 2]
[3, 4, 1, 2]
[4, 3, 1, 2]
[2, 3, 4, 1]
[3, 2, 4, 1]
[2, 4, 3, 1]
[4, 2, 3, 1]
[3, 4, 2, 1]
[4, 3, 2, 1]