Python排列递归

Question

我正在尝试使用回溯法解决问题，我需要它的数字排列。我有执行此操作的基本算法，但问题是……结果不按正常顺序出现。

def perm(a,k=0):
   if(k==len(a)):
      print(a)
   else:
      for i in range(k,len(a)):
         a[k],a[i] = a[i],a[k]
         perm(a, k+1)
         a[k],a[i] = a[i],a[k]

示例:对于 [1,2,3]，正常结果为:[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3, 1,2] [3,2,1]

而此算法将交换最后 2 个元素。我明白为什么。我只是不知道如何纠正这个问题。

我不想使用 itertools 的排列组合。上面的代码可以轻松修复以正常工作吗？从上面看，这个算法的复杂度是多少？

Answer 1

一个递归生成器函数，它按照与原始列表相关的预期顺序生成排列:

def perm(a):
    if len(a) <= 1:
        yield a
    else:
        for i in xrange(len(a)):
            for p in perm(a[:i]+a[i+1:]):
                yield [a[i]]+p

a = [1, 2, 3]

for p in perm(a):
    print(p)

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