- 问题描述
- 分析
- 交换元素
- 循环
- 递归
- 递归条件
- 递归的组成
- 注解
- 代码
输入正整数n,对[1,n]进行全排列并打印所有结果。
全排列的实质,是交换数组中两两元素位置,每个交换后的数组都是原数组的全排列。
交换一次后的数组需要再次交换后续位置的元素,循环一次能轻易实现。
前两步完成后的数组并不包括所有结果,因为不交换元素位置也是一种排列,所以在每次交换元素后,都应该分支出两种选择:交换和不交换。
因为要得到所有结果,循环次数远远不够,此时想到递归所有位置。
递归与分治是密不可分的,递归要求大问题能分解成解决思路一致的小问题,且从最小问题开始结果的回归,通过先解决小问题的方式解决大问题。
递归函数由两部分组成,递归出口和递归模式。
- 递归出口
递归出口决定递归函数何时开始回归,是最小子问题的解。
本题目中递归函数的作用是打印n个数的全排列,那么最小子问题就是打印一个数的全排列,即它本身,这就是递归出口。
- 递归模式
递归模式是处理小问题的通用方法。递归出口能轻松定义,执行递归出口后递归函数结束”递“的过程,开始“归”,递归模式实现的就是如何由子问题的解得到通用解的问题。
注解本题中递归出口得到数组最后一个数的全排列,递归模式则要把解推广到n个数。
考虑末尾两个数的全排列,容易想到交换两个数位置之前和之后进行递归,这样就产生两种结果——交换和不交换,推而广之,就是n个数的全排列。
- 递归还需要传递位置参数k+1,表示每次递归待交换元素的位置。
- 但是光这些还不够,回到之前说的循环,交换元素后进行递归,得到的是交换后的排列,那交换前的呢?
- 再将元素交换回原位置即可。
因此在交换元素位置后,首先调用递归函数对后续位置进行全排列,再在当前循环内将元素交换回原位置,使得之后的循环能继续交换后续元素,继续递归后续元素。
- 所有递归函数是从递归出口开始返回的,所以每个递归出口都对应一个全排列结果,因此可以在递归出口使用数组添加结果。
- 由于Python中可变类型(特别是列表)参数传递的特性:引用传递,函数内修改列表也会改变函数外的列表,故必须使用列表切片[:],否则所有列表值将与最后一次的交换结果相同。
#输入正整数n,对[1,n]进行全排列并打印所有结果
def permute(nums) :
'''嵌套函数'''
def permutation(nums,k,n):#递归边界条件/递归出口
if k==n:
return res.append(nums[:])
for i in range(k,n):#递归模式/递归体
nums[i],nums[k]=nums[k],nums[i]#循环中将k及之后位置的数与k位置的数交换
permutation(nums,k+1,n)#调用递归函数,对k之后所有元素进行上述 *** 作
nums[i],nums[k]=nums[k],nums[i]#保持数组值不变,继续下次循环
res=[]
permutation(nums,0,len(nums))
return res
n=int(input('输入n的值:'))#建议不要超过4,A(5,5)=5=5*4*3*2=120种
a=[i for i in range(1,n+1)]
print(permute(a))
水平有限,欢迎指正!
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)