python求一个字符串的所有排列的实现方法
题目描述：
设计一个程序，当输入一个字符串时，要求输出这个字符串的所有排列。
例如输入字符串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/envpython3
#-*-coding:utf-8-*-
#@Time:2020/2/39:49
#@Author:buu
#@Software:PyCharm
#@Blog：https://blog.csdn.net/weixin_44321080
defswap(str,i,j):
#交换字符数组下标为i和j对应的字符
tmp=str[i]
str[i]=str[j]
str[j]=tmp
defpermutation(str,start):
"""
对字符串中的字符进行全排列
:paramstr:待排序的字符串,list
:paramstart:待排序的子字符串的首字符下标
:return:
"""
ifstr==Noneorstart<0:
return
ifstart==len(str)-1:
#完成全排列后输出当前排列的字符串
print(''.join(str),end='')
else:
i=start
whilei
结果：
算法性能分析：
假设这种方法所需的基本操作数为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/envpython3
#-*-coding:utf-8-*-
#@Time:2020/2/310:37
#@Author:buu
#@Software:PyCharm
#@Blog：https://blog.csdn.net/weixin_44321080
#!/usr/bin/envpython3
#-*-coding:utf-8-*-
#@Time:2020/2/39:49
#@Author:buu
#@Software:PyCharm
#@Blog：https://blog.csdn.net/weixin_44321080
defswap(str,i,j):
#交换字符数组下标为i和j对应的字符
tmp=str[i]
str[i]=str[j]
str[j]=tmp
defisDuplicate(str,begin,end):
"""
判断[begin,end)区间中是否有字符与*end相等
:parambegin:指向字符的指针
:paramend:指向字符的指针
:return:如果有相等的字符True，elseFalse
"""
i=begin
whilei
结果：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。