python非递归全排列实现方法

当我们需要对一个列表进行全排列时，通常会使用递归的方法，但是递归的深度随着列表长度的增加而增加，可能会导致栈溢出的问题。因此，我们可以使用非递归的方法实现列表的全排列。

下面是使用Python实现非递归全排列的完整攻略：

问题描述

给定一个列表nums，求出它的全排列。列表中元素不重复，且元素个数小于等于10。

示例输入：[1,2,3]

示例输出：

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

解决方法

1.交换法

我们可以用交换的方式对列表进行全排列。

具体实现步骤如下：

1. 初始化一个res列表用来存储全排列结果,初始化一个stack列表用来模拟递归栈。

2. 把初始列表nums入栈（列表中的元素均未交换）

3. 当栈不为空时，弹出一个元素，初始化一个used集合，表示当前所取过的元素。

4. 对于弹出的元素，从0开始遍历到最后一个元素，如果这个元素没有被取过，那么就交换元素并把它入栈，否则跳过。

5. 如果遍历到了列表的末尾，把当前元素存储到res列表中。

6. 重复执行3-5步，直到栈为空。

def permute(nums):
    res = []
    stack = [(nums, 0)]
    while stack:
        lst, i = stack.pop()
        if i == len(lst):
            res.append(lst)
        else:
            used = set()
            for j in range(i, len(lst)):
                if lst[j] not in used:
                    used.add(lst[j])
                    lst[i], lst[j] = lst[j], lst[i]
                    stack.append((lst[:], i + 1))
                    lst[i], lst[j] = lst[j], lst[i]
    return res

2. 迭代法

迭代法相对于交换法来说实现代码更加简洁。

具体实现步骤如下:

1. 定义一个生成器函数gen(nums)。

2. 首先定义一个长度为n（n为nums中元素个数）的数组p，用来存储当前输出排列。

1） 首先将每个元素的前一个元素下标存入p，并把p[0]设置为-1，指示结束排列。

2） 将每个元素i前面的所有元素集合A放入字典D中，并用0初始化，用于记录集合A已输出排列的数量。

例如，对于列表[1,2,3]，字典D应该为{1:0, 2:0, 3:0}。

1. 在gen函数中使用while循环遍历，每次得到一个排列，然后在p中查找字典D对应集合已经输出的排列数量加一，然后再继续查找，依次类推直到数字排列结束。

def gen(nums):
    n = len(nums)
    p = [-1] + list(range(n-1))
    D = {i:0 for i in nums}
    yield [nums[p[i+1]] for i in range(n-1)]
    i = 0
    while i < n-1:
        D[nums[p[i+1]]] += 1
        while p[i+1] < i + 1:
            p[i+1] += 1
        if D[nums[p[i+1]]] < i + 1:
            p[i+1], p[i+D[nums[p[i+1]]]+1] = p[i+D[nums[p[i+1]]]+1], p[i+1]
            yield [nums[p[i+1]]] + [nums[p[j+1]] for j in range(i)]
            i = 0
        else:
            p[i+1:] = [p[i]] + p[i+1:-1]
            i += 1

def permute(nums):
    return [x for x in gen(nums)]

示例说明

例如，对于列表[1,2,3]，我们可以分别使用上述的两个方法来得到全排列。

使用交换法：

nums = [1,2,3]
print(permute(nums))

输出:

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

使用迭代法：

nums = [1,2,3]
print(permute(nums))

输出:

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

可以看到，输出结果都是正确的。