document.write('这道题主要考察对递归的理解，可以采用递归的方法来实现。当然也可以使用非递归的方法来实现，但是与
递归法相比，非递归法难度增加了很多。下面分别介绍这两种方法。
方法一：递归法
下面以字符串abc为例介绍对字符串进行全排列的方法。具体步骤如下：
(1)首先固定第一个字符a，然后对后面的两个字符b与c进行全排列；
(2)交换第一个字符与其后面的字符，即交换a与b，然后固定第一个字符b，接着对后面的两个字符a与c进
行全排列；
(3)由于第(2)步交换了a和b破坏了字符串原来的顺序，因此，需要再次交换a和b使其恢复到原来的顺序，
然后交换第一个字符与第三个字符(交换a和c)，接着固定第一个字符c，对后面的两个字符a与b求全排列。
在对字符串求全排列的时候就可以采用递归的方式来求解，实现方法如下图所示：
在使用递归方法求解的时候，需要注意以下两个问题：(1)逐渐缩小问题的规模，并且可以用同样的方法来
求解子问题；(2)递归一定要有结束条件，否则会导致程序陷入死循环。本题目递归方法实现代码如下：
#交换字符数组下标为i和j对应的字符
def swap(str,i,j):
tmp=str[i]
str[i]=str[j]
str[j]=tmp
"""
方法功能: 对字符串中的字符进行全排列
输入参数: str为待排序的字符串, start为待排序的子字符串的首字符下标
"""
def Permutation(str,start):
if str==None or start＜0:
return
#完成全排列后输出当前排列的字符串
if start==len(str)-1:
print ".join(str),
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)
程序的运行结果为：
abc acb bac bca cba cab
算法性能分析：
假设这种方法需要的基本操作数为f(n)，那么f(n)=n*f(n-1)=n*(n-1)*f(n-2)…=n!。所以，算法的时间复杂
度为O(n!)。算法在对字符进行交换的时候用到了常量个指针变量，因此，算法的空间复杂度为O(1)。
方法二：非递归法
递归法比较符合人的思维，因此，算法的思路以及算法实现都比较容易。下面介绍另外一种非递归的方
法。算法的主要思想为：从当前字符串出发找出下一个排列(下一个排列为大于当前字符串的最小字符串)。
通过引入一个例子来介绍非递归算法的基本思想：假设要对字符串“12345”进行排序。第一个排列一定
是“12345”，依此获取下一个排列："12345"-＞"12354"-＞"12435"-＞"12453"-＞"12534"＞"12543"-
＞"13245"-＞…。从“12543”->“13245”可以看出找下一个排列的主要思路为：(1)从右到左找到两个相
邻递增(从左向右看是递增的)的字符串，例如“12543”，从右到左找出第一个相邻递增的子串为“25”；
记录这个小的字符的下标为pmin；(2)找出pmin后面的比它大的最小的字符进行交换，在本例中‘2’后面
的子串中比它大的最小的字符为‘3’，因此，交换‘2’和‘3’得到字符串“13542”；(3)为了保证下一
个排列为大于当前字符串的最小字符串，在第(2)步中完成交换后需要对pmin后的子串重新组合，使其值最
小，只需对pmin后面的字符进行逆序即可(因为此时pmin后面的子字符串中的字符必定是按照降序排列，逆
序后字符就按照升序排列了)，逆序后就能保证当前的组合是新的最小的字符串。在这个例子中，上一步得到
的字符串为“13542”，pmin指向字符‘3’，对其后面的子串“542”逆序后得到字符串“13245”；(4)
当找不到相邻递增的子串时，说明找到了所有的组合。
需要注意的是，这种方法适用于字符串中的字符是按照升序排列的情况。因此，非递归方法的主要思路
为：(1)首先对字符串进行排序(按字符进行升序排列)；(2)依次获取当前字符串的下一个组合直到找不到相邻
递增的子串为止。实现代码如下：
#交换字符数组下标为i和j对应的字符
def swap(str,i,j):
tmp=str[i]
str[i]=str[j]
str[j]=tmp
"""
方法功能: 翻转字符串
输入参数: begin与end分别为字符串的第一个字符与最后一个字符的下标
"""
def Reverse(str,begin,end):
i=begin
j=end
while i＜j:
swap(str,i,j)
i+=1
j-=1
"""
方法功能: 根据当前字符串的组合
输入参数: str:字符数组
返回值: 还有下一个组合返回True, 否则返回False
"""
def getNextPermutation(str):
end=len(str)-1 #字符串最后一个字符的下标
cur=end #用来从后向前遍历字符串
suc=0 #cur的后继
tmp=0
while cur!=0:
# 从后向前开始遍历字符串
suc=cur
cur-=1
if str[cur]＜str[suc]:
#相邻递增的字符, cur指向较小的字符
#找出cur后面最小的字符tmp
tmp=end
while str[tmp]＜str[cur]:
tmp-=1
#交换cur与tmp
swap(str,cur,tmp)
#把cur后面的子字符串进行翻转
Reverse(str,suc,end)
return True
return False
"""
方法功能: 获取字符串中字符的所有组合
输入参数: str:字符数组
"""
def Permutation (s):
if s==None or len(s)＜1:
print "参数不合法"
return
str=list(s)
str.sort() #升序排列字符数组
print str
print ".join(str),
while getNextPermutation(str):
print ".join(str),
if __name__=="__main__":
s="abc"
Permutation(s)
程序的运行结果为：
abc acb bac bca cab cba
算法性能分析：
首先对字符串进行排序的时间复杂度为O(n2)，接着求字符串的全排列，由于长度为n的字符串全排列个数为n!，因此Permutation函数中的循环执行的次数为n!，循环内部调用函数getNextPermutation，getNextPermutation内部用到了双重循环，因此它的时间复杂度为O(n2)。所以求全排列算法的时间复杂度为O(n!*n2)。
');
![\"360截图20190815155042048.jpg\"](\"http://www.alatiku.com/d/file/shiti/f2000ecea94a7c061a7736a6d8a59607.jpg\")