快捷導(dǎo)航

python求一個(gè)字符串的所有排列的實(shí)現(xiàn)方法

更新時(shí)間：2020年02月04日 14:29:18 作者：布?xì)W不歐

這篇文章主要介紹了python求一個(gè)字符串的所有排列的實(shí)現(xiàn)方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

題目描述：

設(shè)計(jì)一個(gè)程序，當(dāng)輸入一個(gè)字符串時(shí)，要求輸出這個(gè)字符串的所有排列。
例如輸入字符串 abc，要求輸出由字母 a、b、c 所能排列出來(lái)的所有字符串 abc，acb，bac，bca，cab，cba。

方法：遞歸法

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

在使用遞歸求解的時(shí)候，要注意：
(1) 逐漸縮小問(wèn)題的規(guī)模，并且可以用同樣的方法來(lái)求解子問(wèn)題；
(2) 遞歸一定要有結(jié)束條件，否則會(huì)導(dǎo)致程序陷入死循環(huán)；

代碼實(shí)現(xiàn)：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/2/3 9:49
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
def swap(str, i, j):
  # 交換字符數(shù)組下標(biāo)為i和j對(duì)應(yīng)的字符
  tmp = str[i]
  str[i] = str[j]
  str[j] = tmp


def permutation(str, start):
  """
  對(duì)字符串中的字符進(jìn)行全排列
  :param str: 待排序的字符串,list
  :param start: 待排序的子字符串的首字符下標(biāo)
  :return:
  """
  if str == None or start < 0:
    return
  if start == len(str) - 1:
    # 完成全排列后輸出當(dāng)前排列的字符串
    print(''.join(str),end=' ')
  else:
    i = start
    while i < len(str):
      # 交換start與i所在位置的字符
      swap(str, start, i)
      # 固定第一個(gè)字符，對(duì)剩余的字符進(jìn)行全排列
      permutation(str, start + 1)
      # 還原start與i所在位置的字符
      swap(str, start, i)
      i += 1


def permutation_transe(s):
  str = list(s)
  permutation(str, 0)


if __name__ == '__main__':
  s = 'abc'
  permutation_transe(s)

結(jié)果：

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

引申：

如何去掉重復(fù)的排列？
當(dāng)字符串中沒(méi)有重復(fù)的字符的時(shí)候，它的所有組合對(duì)應(yīng)的字符串就沒(méi)有重復(fù)的情況；當(dāng)時(shí)當(dāng)字符串中有重復(fù)的字符的時(shí)候，例如 ‘baa'，此時(shí)如果按照上面介紹的算法求全排列會(huì)有重復(fù)的字符串。

思路：
全排列的主要思路為：從第一個(gè)字符起每個(gè)字符分別與它們后面的字符進(jìn)行交換：例如對(duì)于“baa”，交換 baa 第一個(gè)與第二個(gè)字符后得到“aba”，再考慮交換 baa 第一個(gè)與第三個(gè)字符后得到“aab”，由于 baa 的第二個(gè)字符與第三個(gè)字符相等，所以會(huì)導(dǎo)致兩種交換方式得到的 aba 與 aab 對(duì)應(yīng)的全排列是重復(fù)的（在固定aba與aab的第一個(gè)字符的情況下，它們對(duì)應(yīng)的全排列都為 aba，aab）。
所以可以知道，去掉重復(fù)排列的主要思路為：
從第一個(gè)字符起，每個(gè)字符分別與它后面的非重復(fù)出現(xiàn)的字符進(jìn)行交換。在遞歸的基礎(chǔ)上只需要增加一個(gè)判斷字符是否重復(fù)出現(xiàn)的函數(shù)即可。

代碼實(shí)現(xiàn)：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/2/3 10:37
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# @Time  : 2020/2/3 9:49
# @Author : buu
# @Software: PyCharm
# @Blog  ：https://blog.csdn.net/weixin_44321080
def swap(str, i, j):
  # 交換字符數(shù)組下標(biāo)為i和j對(duì)應(yīng)的字符
  tmp = str[i]
  str[i] = str[j]
  str[j] = tmp

def isDuplicate(str,begin,end):
  """
  判斷 [begin,end)區(qū)間中是否有字符與 *end相等
  :param begin: 指向字符的指針
  :param end: 指向字符的指針
  :return: 如果有相等的字符True，else False
  """
  i=begin
  while i<end:
    if str[i]==str[end]:
      return True
    else:
      i+=1
  return False


def permutation(str, start):
  """
  對(duì)字符串中的字符進(jìn)行全排列
  :param str: 待排序的字符串,list
  :param start: 待排序的子字符串的首字符下標(biāo)
  :return:
  """
  if str == None or start < 0:
    return
  if start == len(str) - 1:
    # 完成全排列后輸出當(dāng)前排列的字符串
    print(''.join(str),end=' ')
  else:
    i = start
    while i < len(str):
      # 若有重復(fù)字符，則終止當(dāng)前循環(huán)，開(kāi)始下一次循環(huán)
      if isDuplicate(str,start,i):
        i+=1
        continue
      # 交換start與i所在位置的字符
      swap(str, start, i)
      # 固定第一個(gè)字符，對(duì)剩余的字符進(jìn)行全排列
      permutation(str, start + 1)
      # 還原start與i所在位置的字符
      swap(str, start, i)
      i += 1


def permutation_transe(s):
  str = list(s)
  permutation(str, 0)


if __name__ == '__main__':
  s = 'baa'
  permutation_transe(s)

結(jié)果：