Python中固定前一元素的置换

Question

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

编辑

以下是我的问题的重新表述： 你能想象一个树图吗？所以，第一级-它是一个顶部（也称为父级）顶点。所以，如果我们有类似于[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.1lvl并修复了n-2元素（正如您可以看到的那样，没有必要修复第一个元素）。因此，在这个层次上，我们固定了3，和{}，这是n-1第n个元素，输出是：

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

1.1.1.2等级

我们已经在这里完成了，但还没有完成。升一级（1.1.2级）。然后进行置换。这里我们已经修复了n-1第个元素（它是2）和nth（它是4）

1.1.2.1等级

1.1.2.2等级

在这里完成。转到上层。这里修复了1和{}。所以

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

1.1.3.2等级

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

所以，问题是：如何在python中实现这一点？在

Answer 1

我希望这就是您想要的：我更喜欢使用索引0,1,2,3而不是1,2,3,4

def switch(a,b,c):
    aux = a[b]
    a[b] = a[c]
    a[c] = aux
class perm():
    def __init__(self,mylist,txt,myreference,flag = None):
        self.mylist = []
        self.mylist.extend(mylist)
        self.myreference = myreference
        self.txt = txt
        if flag == None:
            print self.mylist,txt
    def make_perm(self):
        count = 0
        if self.myreference > 1:
            New = perm(self.mylist,self.txt+str(count),self.myreference-1,0)
            New.make_perm()
        for i in xrange(self.myreference-1,-1,-1):
            switch(self.mylist,i,self.myreference)
            count += 1
            New = perm(self.mylist,self.txt+str(count),self.myreference-1)
            New.make_perm()

N = 4            
A = perm(range(N),"",N-1)
A.make_perm()

我希望你认识到，一旦我们在[1，2，4，3]上，并且我们把3固定在第4个位置，那么如果不修改3的位置，就不能继续1，4，2，3在永磁体上移动。在

Answer 2

结果中的排列通过交换两个元素而与前一个元素不同。在

交换两个元素对应于一个永久自一体体中的一条边。在

这表明您正试图根据某些条件访问置换自一体体中的顶点。你能用几何术语解释一下这些标准是什么吗？在

例如，一个可能的问题是如何通过在每个回合交换两个元素来生成所有可能的排列。这相当于在全自动体上找到一条哈密顿路径。这个问题的答案是由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]

跑步

^{pr2}$

打印以下内容：

[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]

Answer 3

您可以始终使用itertools.permutations。在

from itertools import permutations
perm = permutations([1, 2, 3, 4])
while True:
    try:
        print perm.next() # perm.next() gives a tuple of the next permutation
    except StopIteration:
        break