python实现全排列（递归和循环） |
您所在的位置：网站首页 › 全排列递归算法理解 › python实现全排列（递归和循环） |
|
1.利用itertools库中的permutations方法
import itertools
# 利用itertools库中的permutations函数,给定一个排列,输出他的全排列
def allPermutation(n):
permutation = []
# 首先需要初始化一个1-n的排列
for i in range(n):
permutation.append(i+1)
# itertools.permutations返回的只是一个对象,需要将其转化成list
# 每一种排列情况以元组类型存储
all_permutation = list(itertools.permutations(permutation))
return all_permutation
print(allPermutation(4))
"""
输出:
[(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2),
(2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1),
(3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1),
(4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)]
"""
2.递归
对于n个数的全排列问题，根据递归的思想，可以将其转化为： 已经确定了第一个位置上的数，求后面n-1个数的全排列 而对于n-1个数的全排列，也只需确定第一个数，考虑后面n-2个数的全排列 …… 以此类推 具体实现过程如下（以4个数为例，用①②③④来表示各层递归及回溯的过程）： 初始时为[1,2,3,4]，现在以它为起点，通过改变各个数字位置来得到其他排列 ①把[1,2,3,4]的第一个数（也就是1）和第一个数做交换（后续解释为什么要自己跟自己换），确定第一个数字为1，然后递归求出[2,3,4]的全排列，此时，我们得到的排列是[1,[2,3,4]]（[2,3,4]表示2,3,4这三个数的任意一种排列情况） ②把[2,3,4]的第一个数（也就是2）和第一个数做交换，确定第一个数是2，然后求[3,4]的全排列，此时，得到[1,2,[3,4]] ③把[3,4]的第一个数（也就是3）和第一个数做交换，确定第一个数是3，然后求4的全排列，此时得到[1,2,3,4] ④由于只剩下一个数4了（这里可以作为递归结束的标志），所以[1,2,3,4]就是一种排列，这时回溯到上一步（即第③步，确定第一个数是3的地方） ③回溯到这一步时，我们得到的是[1,2,[3,4]]，这时把[3,4]的第一个数（3）和第二个数（4）做交换，即确定第一个数为4，然后求3的全排列，此时得到[1,2,4,3]（上面之所以要把第一个数和第一个数做交换，而没有直接交换第一和第二个数，是因为，如果直接交换第一、二个数，那我们就只能得到[4,3]的结果，而无法得到[3,4]） ④此时还是只剩下一个数3，递归结束，回溯到上一步（③） ③实际上这一步并不存在，因为再回到这一步时，我们想要将3和后面的数交换发现没有已经没有需要交换的数了，那么我们可以设置一个循环，循环次数就是交换次数，循环退出时会回溯到上一步（即第②步） ②回溯到这一步时，我们得到的是[1,[2,3,4]]，这时把[2,3,4]的第一个数（2）和第二个数交换（3），也就是确定第一个数为3，然后求[2,4]的全排列 ③把[2,4]的第一个数（2）和第一个数交换（2），得到[1,3,2,4]，剩下一个4，回溯到上一步（具体步骤省略，同上） ③把[2,4]的第一个数（2）和第二个数交换（4），得到[1,3,4,2]，剩下一个2，回溯到上一步（具体步骤省略，同上） ③跳出循环，回溯 ②此时还是[1,[2,3,4]]，但是要把[2,3,4]的第一个数（2）和第三个数（4）做交换，即确定第一个数是4，然后求[2,3]的全排列 ③交换2和2，[1,4,2,3] ③交换2和3，[1,4,3,2] ③跳出循环，回溯 ②此时还是[1,[2,3,4]]，但是已经没有数能和2交换了，所以也是跳出循环，回溯 ①回到这一步时，第一个数字是1的情况已经全部得到了，所以将[1,2,3,4]第一个数字（1）和第二个数字交换（2），即确定第一个数字是2，得到[2,[1,3,4]] ②将第一个数和第一个数交换，[2,1,[3,4]] ③交换3和3，[2,1,3,4] ③交换3和4，[2,1,4,3] ③跳出循环，回溯 ②[2,[1,3,4]]，将第一个数和第二个数交换，得到[2,3,[1,4]] ③交换1和1，[2,3,1,4] ③交换1和4，[2,3,4,1] ③跳出循环，回溯 [2,[1,3,4]]，将第一个数字和第三个数字交换，得到[2,4,[1,3]] ③交换1和1，[2,4,1,3] ③交换1和3，[2,4,3,1] ③跳出循环，回溯 [2,[1,3,4]]，但是已经没有数能和1交换了，跳出循环，回溯 ①此时还是回到[1,2,3,4]，这次交换第一个数（1）和第三个数（3），得到[3,[1,2,4]] 以此类推 import copy # 用一个全局变量记录每次递归得到的结果 All_permutation = [] # 递归函数,arr表示当前的排列,如[1,2,3,4],next表示当前排列中前next个数已经确定,需要从next+1的位置开始交换 # 注意列表下标从0开始,next表示的是下标 # 如next=1时,说明第一个数确定为1,然后从第二个数开始直到列表的结尾,每个数都要与第二个数进行一次交换 def allPermutation(arr, next): # 当next=len(arr)-1时,此时只剩下一个数要排列,直接就是结果 if next == len(arr) - 1: global All_permutation All_permutation.append(arr) else: # 从第next+1个数开始,每个数与第next+1的数进行一次交换(包括自己) for i in range(next, len(arr)): # 深拷贝,避免影响到原来的排列情况 update_permutation = copy.deepcopy(arr) update_permutation[i], update_permutation[next] = update_permutation[next], update_permutation[i] allPermutation(update_permutation, next + 1) allPermutation([1, 2, 3, 4], 0) print(All_permutation) """ [[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], [1, 3, 4, 2], [1, 4, 3, 2], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 3, 4, 1], [2, 4, 3, 1], [2, 4, 1, 3], [3, 2, 1, 4], [3, 2, 4, 1], [3, 1, 2, 4], [3, 1, 4, 2], [3, 4, 1, 2], [3, 4, 2, 1], [4, 2, 3, 1], [4, 2, 1, 3], [4, 3, 2, 1], [4, 3, 1, 2], [4, 1, 3, 2], [4, 1, 2, 3]] """ 3.循环对一个数进行排列时，结果只有一个：1 对两个数进行排列时，将第二个数插进第一个排列的所有可能空位：2，1和1，2（前面和后面） 对三个数进行排列时，将第三个数插进第二个排列的所有可能空位： 将3插进2，1：3，2，1和2，3，1和2，1，3（依次插进前中后） 将3插进1，2：3，1，2和1，3，2和1，2，3（依次插进前中后） 对四个数进行排列时，将第四个数插进第三个排列的所有可能空位： 将4插进3，2，1：4321，3421，3241，3214 将4插进2，3，1：4231，2431，2341，2314 以此类推 import copy def allPermutation(n): # 初始时插入一个元素 all_permutation = [[1]] for i in range(1, n): # 在将一个新的数插入原有排列中时,需要取出原有排列的每一种情况,然后对于每一种情况,又有不同的插入位置 # 并且每一次插入之后得到的新排列都要放进all_permutation中 # 如:将3插进[1,2]和[2,1]时 # 我们需要从all_permutation中出[1,2],将3插进去得到3个新的排列[3,1,2],[1,3,2],[1,2,3] # 再将这三个新的排列放回all_permutation,并且原来all_permutation中的[1,2]要被删除 # 故这里用一个update_permutation来对总的排列进行更新all_permutation # 注意在循环结束前要把update_permutation的值再赋给all_permutation update_permutation = [] # 插入元素之前,先看看截止上一步一共得到了多少个全排列,对每一种情况进行插入 len1 = len(all_permutation) for j in range(len1): # 取出第j个排列,统计它有多少个空位,空位数=排列中元素个数+1,将i插进所有空位 len2 = len(all_permutation[j]) + 1 for k in range(len2): # 这里每次都需要取出第j种排列并对其进行插入,故进行一个列表的拷贝 # 避免这一次插入后的all_permutation[j]会产生变化,影响下一次循环 perm = copy.deepcopy(all_permutation[j]) perm.insert(k, i + 1) update_permutation.append(perm) all_permutation = update_permutation return all_permutation print(allPermutation(4)) """ 输出: [[4, 3, 2, 1], [3, 4, 2, 1], [3, 2, 4, 1], [3, 2, 1, 4], [4, 2, 3, 1], [2, 4, 3, 1], [2, 3, 4, 1], [2, 3, 1, 4], [4, 2, 1, 3], [2, 4, 1, 3], [2, 1, 4, 3], [2, 1, 3, 4], [4, 3, 1, 2], [3, 4, 1, 2], [3, 1, 4, 2], [3, 1, 2, 4], [4, 1, 3, 2], [1, 4, 3, 2], [1, 3, 4, 2], [1, 3, 2, 4], [4, 1, 2, 3], [1, 4, 2, 3], [1, 2, 4, 3], [1, 2, 3, 4]] """ |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |