当我们需要对一个列表进行全排列时,通常会使用递归的方法,但是递归的深度随着列表长度的增加而增加,可能会导致栈溢出的问题。因此,我们可以使用非递归的方法实现列表的全排列。
下面是使用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.交换法
我们可以用交换的方式对列表进行全排列。
具体实现步骤如下:
-
初始化一个res列表用来存储全排列结果,初始化一个stack列表用来模拟递归栈。
-
把初始列表nums入栈(列表中的元素均未交换)
-
当栈不为空时,弹出一个元素,初始化一个used集合,表示当前所取过的元素。
-
对于弹出的元素,从0开始遍历到最后一个元素,如果这个元素没有被取过,那么就交换元素并把它入栈,否则跳过。
-
如果遍历到了列表的末尾,把当前元素存储到res列表中。
-
重复执行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. 迭代法
迭代法相对于交换法来说实现代码更加简洁。
具体实现步骤如下:
-
定义一个生成器函数gen(nums)。
-
首先定义一个长度为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}。
- 在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]]
可以看到,输出结果都是正确的。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:python非递归全排列实现方法 - Python技术站