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]]
"""