【Python】字符串的全排列（递归、非递归）

旧城等待， 2022-05-22 03:11 241阅读 0赞

### 字符串的全排列 ###

> 给定字符串S\[0…N-1\]，设计算法，枚举S的全排列

#### 一、递归方式 ####

分析思路：

> 把s\[0\]固定在位置0上，\[1,n-1\]位置的数字全排（递归）  
> 把s\[1\]固定在位置0上（把s\[1\]和s\[0\]交换），\[1,n-1\]位置的数字全排（递归）  
> ……  
> 如果第i个数字在前面出现过，则跳过  
> ……  
> 把s\[n-1\]固定在位置0上（把s\[n-1\]和s\[0\]交换），\[1,n-1\]位置的数字全排（递归）

Python代码如下：

from copy import deepcopy
    
    
    def isduplicate(li, n, t):
        """
        从li的位置n到位置t-1，有没有和li[t]相等的数字
        """
        while n < t:
            if li[n] == li[t]:
                return True
            n += 1
        return False
    
    
    def swap(li, i, j):
        if i == j:
            return
        temp = li[j]
        li[j] = li[i]
        li[i] = temp
    
    
    def permutation(li, size, n, result):
        """
        [n,size]位置的数字全排
        :param li:字符串数组
        :param size: 字符串长度
        :param n: 要交换的位置
        :param result: 保留结果
        :return:
        """
    
        if n == size - 1:
            result.append(deepcopy(li))
            return
        for i in list(range(n, size)):  # 分别把(size-n)个数字固定到位置n
            if isduplicate(li, n, i):  # 如果位置n出现过数字li[i]，跳过
                continue
            swap(li, i, n)  # 把s[n]和s[i]交换，把s[i]固定到位置n
            permutation(li, size, n + 1, result)  # [n+1,size-1]位置的数字全排
            swap(li, i, n)  # 把s[n]和s[i]交换回来
    
    
    if __name__ == '__main__':
        li = [1, 2, 2, 3]
        size = len(li)
        n = 0
        result = []
        permutation(li, size, n, result)
        for i in result:
            print(i)

输入结果：

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

字符串的全排列 递归示意图：  
![字符串的全排列 递归示意图][70]

感觉不好想的，可以画个图，有助于理解

--------------------

#### 二、非递归方式 ####

分析思路：

> 起点：字典序最小的排列，例如122345。起点为正序  
> 终点：字典序最大的排列，例如543221。终点为倒序  
> 过程：按当前的排列找出刚好比它大的下一个排列  
> 如：524321的下一个排列是531224  
> 如何计算？  
> 我们从后向前找第一双相邻的递增数字，”21”、”32”、”43”都是非递增的，”24”即满足要求，称前一个数字2为替换数，替换数的下标称为替换点，再从后面找一个比替换数大的最小数（这个数必然存在），1、2都不行，3可以，将3和2交换得到”534221”，然后再将替换点后的字符串”4221”颠倒即得到”531224”。  
> 对于像”543221”这种已经是最“大”的排列，返回false。  
> 这样，一个while循环再加上计算字符串下一个排列的函数就可以实现非递归的全排列算法。

步骤：后找、小大、交换、翻转

> 后找：字符串中最后一个升序的位置i，即：S\[i\]<S\[i+1\]；  
> 查找(小大)：S\[i+1…N-1\]中比S\[i\]大的最小值S\[j\]；  
> 交换：S\[i\]，S\[j\]；交换操作前和操作后，S\[i+1…N-1\]一定都是降序的  
> 翻转：S\[i+1…N-1\]

Python代码如下：

from copy import deepcopy
    
    
    def swap(li, i, j):
        if i == j:
            return
        temp = li[j]
        li[j] = li[i]
        li[i] = temp
    
    
    def reverse(li, i, j):
        """
        翻转
        :param li: 字符串数组
        :param i: 翻转开始位置
        :param j: 翻转结束位置
        """
        if li is None or i < 0 or j < 0 or i >= j or len(li) < j + 1:
            return
        while i < j:
            swap(li, i, j)
            i += 1
            j -= 1
    
    
    def get_next_permutation(li, size):
        # 后找：字符串中最后一个升序的位置i，即：S[i]<S[i+1]
        i = size - 2
        while i >= 0 and li[i] >= li[i + 1]:
            i -= 1
        if i < 0:
            return False
        # 查找(小大)：S[i+1…N-1]中比S[i]大的最小值S[j]
        j = size - 1
        while li[j] <= li[i]:
            j -= 1
        # 交换：S[i]，S[j]
        swap(li, i, j)
        # 翻转：S[i+1…N-1]
        reverse(li, i + 1, size - 1)
        return True
    
    
    if __name__ == '__main__':
        li = [1, 2, 3, 2, 4, 5]
        li.sort()  # 初始的li必须是正序的 [1, 2, 2, 3, 4, 5]
        size = len(li)
        result = [deepcopy(li)]
        while get_next_permutation(li, size):
            result.append(deepcopy(li))
        for i in result:
            print(i)

输出结果：

[1, 2, 2, 3, 4, 5]
    [1, 2, 2, 3, 5, 4]
    [1, 2, 2, 4, 3, 5]
    [1, 2, 2, 4, 5, 3]
    [1, 2, 2, 5, 3, 4]
    [1, 2, 2, 5, 4, 3]
    [1, 2, 3, 2, 4, 5]
    [1, 2, 3, 2, 5, 4]
    [1, 2, 3, 4, 2, 5]
    [1, 2, 3, 4, 5, 2]
    [1, 2, 3, 5, 2, 4]
    [1, 2, 3, 5, 4, 2]
    [1, 2, 4, 2, 3, 5]
    [1, 2, 4, 2, 5, 3]
    [1, 2, 4, 3, 2, 5]
    [1, 2, 4, 3, 5, 2]
    [1, 2, 4, 5, 2, 3]
    [1, 2, 4, 5, 3, 2]
    [1, 2, 5, 2, 3, 4]
    [1, 2, 5, 2, 4, 3]
    [1, 2, 5, 3, 2, 4]
    [1, 2, 5, 3, 4, 2]
    [1, 2, 5, 4, 2, 3]
    [1, 2, 5, 4, 3, 2]
    [1, 3, 2, 2, 4, 5]
    [1, 3, 2, 2, 5, 4]
    [1, 3, 2, 4, 2, 5]
    [1, 3, 2, 4, 5, 2]
    [1, 3, 2, 5, 2, 4]
    [1, 3, 2, 5, 4, 2]
    [1, 3, 4, 2, 2, 5]
    [1, 3, 4, 2, 5, 2]
    [1, 3, 4, 5, 2, 2]
    [1, 3, 5, 2, 2, 4]
    [1, 3, 5, 2, 4, 2]
    [1, 3, 5, 4, 2, 2]
    [1, 4, 2, 2, 3, 5]
    [1, 4, 2, 2, 5, 3]
    [1, 4, 2, 3, 2, 5]
    [1, 4, 2, 3, 5, 2]
    [1, 4, 2, 5, 2, 3]
    [1, 4, 2, 5, 3, 2]
    [1, 4, 3, 2, 2, 5]
    [1, 4, 3, 2, 5, 2]
    [1, 4, 3, 5, 2, 2]
    [1, 4, 5, 2, 2, 3]
    [1, 4, 5, 2, 3, 2]
    [1, 4, 5, 3, 2, 2]
    [1, 5, 2, 2, 3, 4]
    [1, 5, 2, 2, 4, 3]
    [1, 5, 2, 3, 2, 4]
    [1, 5, 2, 3, 4, 2]
    [1, 5, 2, 4, 2, 3]
    [1, 5, 2, 4, 3, 2]
    [1, 5, 3, 2, 2, 4]
    [1, 5, 3, 2, 4, 2]
    [1, 5, 3, 4, 2, 2]
    [1, 5, 4, 2, 2, 3]
    [1, 5, 4, 2, 3, 2]
    [1, 5, 4, 3, 2, 2]
    [2, 1, 2, 3, 4, 5]
    [2, 1, 2, 3, 5, 4]
    [2, 1, 2, 4, 3, 5]
    [2, 1, 2, 4, 5, 3]
    [2, 1, 2, 5, 3, 4]
    [2, 1, 2, 5, 4, 3]
    [2, 1, 3, 2, 4, 5]
    [2, 1, 3, 2, 5, 4]
    [2, 1, 3, 4, 2, 5]
    [2, 1, 3, 4, 5, 2]
    [2, 1, 3, 5, 2, 4]
    [2, 1, 3, 5, 4, 2]
    [2, 1, 4, 2, 3, 5]
    [2, 1, 4, 2, 5, 3]
    [2, 1, 4, 3, 2, 5]
    [2, 1, 4, 3, 5, 2]
    [2, 1, 4, 5, 2, 3]
    [2, 1, 4, 5, 3, 2]
    [2, 1, 5, 2, 3, 4]
    [2, 1, 5, 2, 4, 3]
    [2, 1, 5, 3, 2, 4]
    [2, 1, 5, 3, 4, 2]
    [2, 1, 5, 4, 2, 3]
    [2, 1, 5, 4, 3, 2]
    [2, 2, 1, 3, 4, 5]
    [2, 2, 1, 3, 5, 4]
    [2, 2, 1, 4, 3, 5]
    [2, 2, 1, 4, 5, 3]
    [2, 2, 1, 5, 3, 4]
    [2, 2, 1, 5, 4, 3]
    [2, 2, 3, 1, 4, 5]
    [2, 2, 3, 1, 5, 4]
    [2, 2, 3, 4, 1, 5]
    [2, 2, 3, 4, 5, 1]
    [2, 2, 3, 5, 1, 4]
    [2, 2, 3, 5, 4, 1]
    [2, 2, 4, 1, 3, 5]
    [2, 2, 4, 1, 5, 3]
    [2, 2, 4, 3, 1, 5]
    [2, 2, 4, 3, 5, 1]
    [2, 2, 4, 5, 1, 3]
    [2, 2, 4, 5, 3, 1]
    [2, 2, 5, 1, 3, 4]
    [2, 2, 5, 1, 4, 3]
    [2, 2, 5, 3, 1, 4]
    [2, 2, 5, 3, 4, 1]
    [2, 2, 5, 4, 1, 3]
    [2, 2, 5, 4, 3, 1]
    [2, 3, 1, 2, 4, 5]
    [2, 3, 1, 2, 5, 4]
    [2, 3, 1, 4, 2, 5]
    [2, 3, 1, 4, 5, 2]
    [2, 3, 1, 5, 2, 4]
    [2, 3, 1, 5, 4, 2]
    [2, 3, 2, 1, 4, 5]
    [2, 3, 2, 1, 5, 4]
    [2, 3, 2, 4, 1, 5]
    [2, 3, 2, 4, 5, 1]
    [2, 3, 2, 5, 1, 4]
    [2, 3, 2, 5, 4, 1]
    [2, 3, 4, 1, 2, 5]
    [2, 3, 4, 1, 5, 2]
    [2, 3, 4, 2, 1, 5]
    [2, 3, 4, 2, 5, 1]
    [2, 3, 4, 5, 1, 2]
    [2, 3, 4, 5, 2, 1]
    [2, 3, 5, 1, 2, 4]
    [2, 3, 5, 1, 4, 2]
    [2, 3, 5, 2, 1, 4]
    [2, 3, 5, 2, 4, 1]
    [2, 3, 5, 4, 1, 2]
    [2, 3, 5, 4, 2, 1]
    [2, 4, 1, 2, 3, 5]
    [2, 4, 1, 2, 5, 3]
    [2, 4, 1, 3, 2, 5]
    [2, 4, 1, 3, 5, 2]
    [2, 4, 1, 5, 2, 3]
    [2, 4, 1, 5, 3, 2]
    [2, 4, 2, 1, 3, 5]
    [2, 4, 2, 1, 5, 3]
    [2, 4, 2, 3, 1, 5]
    [2, 4, 2, 3, 5, 1]
    [2, 4, 2, 5, 1, 3]
    [2, 4, 2, 5, 3, 1]
    [2, 4, 3, 1, 2, 5]
    [2, 4, 3, 1, 5, 2]
    [2, 4, 3, 2, 1, 5]
    [2, 4, 3, 2, 5, 1]
    [2, 4, 3, 5, 1, 2]
    [2, 4, 3, 5, 2, 1]
    [2, 4, 5, 1, 2, 3]
    [2, 4, 5, 1, 3, 2]
    [2, 4, 5, 2, 1, 3]
    [2, 4, 5, 2, 3, 1]
    [2, 4, 5, 3, 1, 2]
    [2, 4, 5, 3, 2, 1]
    [2, 5, 1, 2, 3, 4]
    [2, 5, 1, 2, 4, 3]
    [2, 5, 1, 3, 2, 4]
    [2, 5, 1, 3, 4, 2]
    [2, 5, 1, 4, 2, 3]
    [2, 5, 1, 4, 3, 2]
    [2, 5, 2, 1, 3, 4]
    [2, 5, 2, 1, 4, 3]
    [2, 5, 2, 3, 1, 4]
    [2, 5, 2, 3, 4, 1]
    [2, 5, 2, 4, 1, 3]
    [2, 5, 2, 4, 3, 1]
    [2, 5, 3, 1, 2, 4]
    [2, 5, 3, 1, 4, 2]
    [2, 5, 3, 2, 1, 4]
    [2, 5, 3, 2, 4, 1]
    [2, 5, 3, 4, 1, 2]
    [2, 5, 3, 4, 2, 1]
    [2, 5, 4, 1, 2, 3]
    [2, 5, 4, 1, 3, 2]
    [2, 5, 4, 2, 1, 3]
    [2, 5, 4, 2, 3, 1]
    [2, 5, 4, 3, 1, 2]
    [2, 5, 4, 3, 2, 1]
    [3, 1, 2, 2, 4, 5]
    [3, 1, 2, 2, 5, 4]
    [3, 1, 2, 4, 2, 5]
    [3, 1, 2, 4, 5, 2]
    [3, 1, 2, 5, 2, 4]
    [3, 1, 2, 5, 4, 2]
    [3, 1, 4, 2, 2, 5]
    [3, 1, 4, 2, 5, 2]
    [3, 1, 4, 5, 2, 2]
    [3, 1, 5, 2, 2, 4]
    [3, 1, 5, 2, 4, 2]
    [3, 1, 5, 4, 2, 2]
    [3, 2, 1, 2, 4, 5]
    [3, 2, 1, 2, 5, 4]
    [3, 2, 1, 4, 2, 5]
    [3, 2, 1, 4, 5, 2]
    [3, 2, 1, 5, 2, 4]
    [3, 2, 1, 5, 4, 2]
    [3, 2, 2, 1, 4, 5]
    [3, 2, 2, 1, 5, 4]
    [3, 2, 2, 4, 1, 5]
    [3, 2, 2, 4, 5, 1]
    [3, 2, 2, 5, 1, 4]
    [3, 2, 2, 5, 4, 1]
    [3, 2, 4, 1, 2, 5]
    [3, 2, 4, 1, 5, 2]
    [3, 2, 4, 2, 1, 5]
    [3, 2, 4, 2, 5, 1]
    [3, 2, 4, 5, 1, 2]
    [3, 2, 4, 5, 2, 1]
    [3, 2, 5, 1, 2, 4]
    [3, 2, 5, 1, 4, 2]
    [3, 2, 5, 2, 1, 4]
    [3, 2, 5, 2, 4, 1]
    [3, 2, 5, 4, 1, 2]
    [3, 2, 5, 4, 2, 1]
    [3, 4, 1, 2, 2, 5]
    [3, 4, 1, 2, 5, 2]
    [3, 4, 1, 5, 2, 2]
    [3, 4, 2, 1, 2, 5]
    [3, 4, 2, 1, 5, 2]
    [3, 4, 2, 2, 1, 5]
    [3, 4, 2, 2, 5, 1]
    [3, 4, 2, 5, 1, 2]
    [3, 4, 2, 5, 2, 1]
    [3, 4, 5, 1, 2, 2]
    [3, 4, 5, 2, 1, 2]
    [3, 4, 5, 2, 2, 1]
    [3, 5, 1, 2, 2, 4]
    [3, 5, 1, 2, 4, 2]
    [3, 5, 1, 4, 2, 2]
    [3, 5, 2, 1, 2, 4]
    [3, 5, 2, 1, 4, 2]
    [3, 5, 2, 2, 1, 4]
    [3, 5, 2, 2, 4, 1]
    [3, 5, 2, 4, 1, 2]
    [3, 5, 2, 4, 2, 1]
    [3, 5, 4, 1, 2, 2]
    [3, 5, 4, 2, 1, 2]
    [3, 5, 4, 2, 2, 1]
    [4, 1, 2, 2, 3, 5]
    [4, 1, 2, 2, 5, 3]
    [4, 1, 2, 3, 2, 5]
    [4, 1, 2, 3, 5, 2]
    [4, 1, 2, 5, 2, 3]
    [4, 1, 2, 5, 3, 2]
    [4, 1, 3, 2, 2, 5]
    [4, 1, 3, 2, 5, 2]
    [4, 1, 3, 5, 2, 2]
    [4, 1, 5, 2, 2, 3]
    [4, 1, 5, 2, 3, 2]
    [4, 1, 5, 3, 2, 2]
    [4, 2, 1, 2, 3, 5]
    [4, 2, 1, 2, 5, 3]
    [4, 2, 1, 3, 2, 5]
    [4, 2, 1, 3, 5, 2]
    [4, 2, 1, 5, 2, 3]
    [4, 2, 1, 5, 3, 2]
    [4, 2, 2, 1, 3, 5]
    [4, 2, 2, 1, 5, 3]
    [4, 2, 2, 3, 1, 5]
    [4, 2, 2, 3, 5, 1]
    [4, 2, 2, 5, 1, 3]
    [4, 2, 2, 5, 3, 1]
    [4, 2, 3, 1, 2, 5]
    [4, 2, 3, 1, 5, 2]
    [4, 2, 3, 2, 1, 5]
    [4, 2, 3, 2, 5, 1]
    [4, 2, 3, 5, 1, 2]
    [4, 2, 3, 5, 2, 1]
    [4, 2, 5, 1, 2, 3]
    [4, 2, 5, 1, 3, 2]
    [4, 2, 5, 2, 1, 3]
    [4, 2, 5, 2, 3, 1]
    [4, 2, 5, 3, 1, 2]
    [4, 2, 5, 3, 2, 1]
    [4, 3, 1, 2, 2, 5]
    [4, 3, 1, 2, 5, 2]
    [4, 3, 1, 5, 2, 2]
    [4, 3, 2, 1, 2, 5]
    [4, 3, 2, 1, 5, 2]
    [4, 3, 2, 2, 1, 5]
    [4, 3, 2, 2, 5, 1]
    [4, 3, 2, 5, 1, 2]
    [4, 3, 2, 5, 2, 1]
    [4, 3, 5, 1, 2, 2]
    [4, 3, 5, 2, 1, 2]
    [4, 3, 5, 2, 2, 1]
    [4, 5, 1, 2, 2, 3]
    [4, 5, 1, 2, 3, 2]
    [4, 5, 1, 3, 2, 2]
    [4, 5, 2, 1, 2, 3]
    [4, 5, 2, 1, 3, 2]
    [4, 5, 2, 2, 1, 3]
    [4, 5, 2, 2, 3, 1]
    [4, 5, 2, 3, 1, 2]
    [4, 5, 2, 3, 2, 1]
    [4, 5, 3, 1, 2, 2]
    [4, 5, 3, 2, 1, 2]
    [4, 5, 3, 2, 2, 1]
    [5, 1, 2, 2, 3, 4]
    [5, 1, 2, 2, 4, 3]
    [5, 1, 2, 3, 2, 4]
    [5, 1, 2, 3, 4, 2]
    [5, 1, 2, 4, 2, 3]
    [5, 1, 2, 4, 3, 2]
    [5, 1, 3, 2, 2, 4]
    [5, 1, 3, 2, 4, 2]
    [5, 1, 3, 4, 2, 2]
    [5, 1, 4, 2, 2, 3]
    [5, 1, 4, 2, 3, 2]
    [5, 1, 4, 3, 2, 2]
    [5, 2, 1, 2, 3, 4]
    [5, 2, 1, 2, 4, 3]
    [5, 2, 1, 3, 2, 4]
    [5, 2, 1, 3, 4, 2]
    [5, 2, 1, 4, 2, 3]
    [5, 2, 1, 4, 3, 2]
    [5, 2, 2, 1, 3, 4]
    [5, 2, 2, 1, 4, 3]
    [5, 2, 2, 3, 1, 4]
    [5, 2, 2, 3, 4, 1]
    [5, 2, 2, 4, 1, 3]
    [5, 2, 2, 4, 3, 1]
    [5, 2, 3, 1, 2, 4]
    [5, 2, 3, 1, 4, 2]
    [5, 2, 3, 2, 1, 4]
    [5, 2, 3, 2, 4, 1]
    [5, 2, 3, 4, 1, 2]
    [5, 2, 3, 4, 2, 1]
    [5, 2, 4, 1, 2, 3]
    [5, 2, 4, 1, 3, 2]
    [5, 2, 4, 2, 1, 3]
    [5, 2, 4, 2, 3, 1]
    [5, 2, 4, 3, 1, 2]
    [5, 2, 4, 3, 2, 1]
    [5, 3, 1, 2, 2, 4]
    [5, 3, 1, 2, 4, 2]
    [5, 3, 1, 4, 2, 2]
    [5, 3, 2, 1, 2, 4]
    [5, 3, 2, 1, 4, 2]
    [5, 3, 2, 2, 1, 4]
    [5, 3, 2, 2, 4, 1]
    [5, 3, 2, 4, 1, 2]
    [5, 3, 2, 4, 2, 1]
    [5, 3, 4, 1, 2, 2]
    [5, 3, 4, 2, 1, 2]
    [5, 3, 4, 2, 2, 1]
    [5, 4, 1, 2, 2, 3]
    [5, 4, 1, 2, 3, 2]
    [5, 4, 1, 3, 2, 2]
    [5, 4, 2, 1, 2, 3]
    [5, 4, 2, 1, 3, 2]
    [5, 4, 2, 2, 1, 3]
    [5, 4, 2, 2, 3, 1]
    [5, 4, 2, 3, 1, 2]
    [5, 4, 2, 3, 2, 1]
    [5, 4, 3, 1, 2, 2]
    [5, 4, 3, 2, 1, 2]
    [5, 4, 3, 2, 2, 1]

[70]: /images/20220522/3be609ed58e44bbfb288bcc88ec90d3b.png