Python中固定前元素的排列组合

Question

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

编辑

这是我问题的重新表述：你能想象一棵树形图吗？第一层是顶层（也叫父节点）顶点。如果我们有一个顶点，比如说[1, 2, 3, 4]，那么我们的下一步就是进行排列，把所有数字插入到n的位置，这意味着我们的输出会是：

1.第一层 [1, 2, 3, 4]

2.第一层 [1, 2, 4, 3]

3.第一层 [1, 3, 4, 2]

4.第一层 [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层，固定n-2元素（如你所见，固定第一个元素没有意义）。所以在这一层我们固定了3和4，也就是n-1和n元素，输出是：

1.1.1.1层 [1, 2, 3, 4]

1.1.1.2层 [2, 1, 3, 4]

我们在这里结束了，但还没有完成。继续往上升到1.1.2层，进行排列。在这里我们固定了n-1元素（就是2）和n元素（就是4）

1.1.2.1层 [1, 3, 2, 4]

1.1.2.2层 [3, 1, 2, 4]

在这里结束。回到上一层。在这里固定了1和4。所以，

1.1.3.1层 [2, 3, 1, 4]

1.1.3.2层 [3, 2, 1, 4]

我们完成了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

你可以使用 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

Answer 3

你得到的排列结果都是通过交换两个元素来得到的，每次交换都会和之前的结果不同。

交换两个元素就像是在一个叫做“排列体”的几何形状上移动。

这说明你可能是在按照某种标准访问这个排列体的顶点。你能用几何的方式解释一下这个标准是什么吗？

举个例子，一个可能的问题是如何通过每次只交换两个元素来生成所有可能的排列。这就相当于在排列体上寻找一条哈密顿路径。这个问题的答案可以通过Steinhaus-Johnson-Trotter算法来解决，它提供了一种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]