溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
題目描述：
設計一個程序，當輸入一個字符串時，要求輸出這個字符串的所有排列。
例如輸入字符串 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_44321080
def swap(str, i, j):
# 交換字符數組下標為i和j對應的字符
tmp = str[i]
str[i] = str[j]
str[j] = tmp
def 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 += 1
def 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'，此時如果按照上面介紹的算法求全排列會有重復的字符串。
思路：
全排列的主要思路為：從第一個字符起每個字符分別與它們后面的字符進行交換：例如對于“baa”，交換 baa 第一個與第二個字符后得到“aba”，再考慮交換 baa 第一個與第三個字符后得到“aab”，由于 baa 的第二個字符與第三個字符相等，所以會導致兩種交換方式得到的 aba 與 aab 對應的全排列是重復的（在固定aba與aab的第一個字符的情況下，它們對應的全排列都為 aba，aab）。
所以可以知道，去掉重復排列的主要思路為：
從第一個字符起，每個字符分別與它后面的非重復出現的字符進行交換。在遞歸的基礎上只需要增加一個判斷字符是否重復出現的函數即可。
代碼實現：
#!/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):
# 交換字符數組下標為i和j對應的字符
tmp = str[i]
str[i] = str[j]
str[j] = tmp
def isDuplicate(str,begin,end):
"""
判斷 [begin,end)區間中是否有字符與 *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):
"""
對字符串中的字符進行全排列
: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):
# 若有重復字符，則終止當前循環，開始下一次循環
if isDuplicate(str,start,i):
i+=1
continue
# 交換start與i所在位置的字符
swap(str, start, i)
# 固定第一個字符，對剩余的字符進行全排列
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)
結果：
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
