題目描述：

設計一個程序，當輸入一個字符串時，要求輸出這個字符串的所有排列。
例如輸入字符串 abc，要求輸出由字母 a、b、c 所能排列出來的所有字符串 abc，acb，bac，bca，cab，cba。

方法：遞歸法

以字符串 abc 為例介紹對字符串進行全排列的方法。
(1) 首先固定第一個字符 a，然后對后面的兩個字符 b、c 進行全排列；
(2) 交換第一個字符與其后面的字符，即交換 a 與 b，然后對后面的兩個字符 a與c 進行全排列；
(3) 由于第二步交換了 a與b 破壞了字符串原來的順序，所以需要再次交換 a與b 使其恢復到原來的順序，然后交換第一個字符與第三個字符（交換a和c），接著固定第一個字符c，對后面的兩個字符 a與b 求全排列。
在對字符串求全排列的時候就可以采用遞歸的方式求解。

在使用遞歸求解的時候，要注意：
(1) 逐漸縮小問題的規模，并且可以用同樣的方法來求解子問題；
(2) 遞歸一定要有結束條件，否則會導致程序陷入死循環；

代碼實現：

#!/usr/bin/env python3# -*- coding: utf-8 -*-# @Time  : 2020/2/3 9:49# @Author : buu# @Software: PyCharm# @Blog  ：https://blog.csdn.net/weixin_44321080def swap(str, i, j):  # 交換字符數組下標為i和j對應的字符  tmp = str[i]  str[i] = str[j]  str[j] = tmpdef permutation(str, start):  """  對字符串中的字符進行全排列  :param str: 待排序的字符串,list  :param start: 待排序的子字符串的首字符下標  :return:  """  if str == None or start < 0:    return  if start == len(str) - 1:    # 完成全排列后輸出當前排列的字符串    print(''.join(str),end=' ')  else:    i = start    while i < len(str):      # 交換start與i所在位置的字符      swap(str, start, i)      # 固定第一個字符，對剩余的字符進行全排列      permutation(str, start + 1)      # 還原start與i所在位置的字符      swap(str, start, i)      i += 1def permutation_transe(s):  str = list(s)  permutation(str, 0)if __name__ == '__main__':  s = 'abc'  permutation_transe(s)

結果：

算法性能分析：
假設這種方法所需的基本操作數為 f(n)，f(n) = n×f(n-1) = …= n!
所以時間復雜度為O(n!)；
空間復雜度為O(1)；

引申：

如何去掉重復的排列？
當字符串中沒有重復的字符的時候，它的所有組合對應的字符串就沒有重復的情況；當時當字符串中有重復的字符的時候，例如 ‘baa'，此時如果按照上面介紹的算法求全排列會有重復的字符串。