Python 中字符串的所有排列（递归）
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/23116911/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
All Permutations of a String in Python (Recursive)
提问by gnp210
I need a kick in the head on this one. I have the following recursive function defined:
我需要在这个上踢一脚。我定义了以下递归函数：
def perms(s):
if(len(s)==1):
return s
res = ''
for x in xrange(len(s)):
res += s[x] + perms(s[0:x] + s[x+1:len(s)])
return res + '\n'
perms("abc") currently returns:
perms("abc") 当前返回：
abccb
bacca
cabba
The desired result is
想要的结果是
abc
acd
bac
bca
cab
cba
Where am I going wrong here? How can I think about this differently to come up with the solution?
我哪里出错了？我如何以不同的方式思考这个问题以提出解决方案？
Note:I am aware of the itertools function. I am trying to understand how to implement permutations recursively for my own learning. That is why I would prefer someone to point out what is wrong with my code, and how to think differently to solve it. Thanks!
注意：我知道 itertools 函数。我试图了解如何为我自己的学习递归地实现排列。这就是为什么我希望有人指出我的代码有什么问题，以及如何以不同的方式思考来解决它。谢谢！
回答by barak manos
There you go (recursive permutation):
你去（递归排列）：
def Permute(string):
if len(string) == 0:
return ['']
prevList = Permute(string[1:len(string)])
nextList = []
for i in range(0,len(prevList)):
for j in range(0,len(string)):
newString = prevList[i][0:j]+string[0]+prevList[i][j:len(string)-1]
if newString not in nextList:
nextList.append(newString)
return nextList
In order to get a list of all permutation strings, simply call the function above with your input string. For example,
为了获得所有排列字符串的列表，只需使用您的输入字符串调用上面的函数。例如，
stringList = Permute('abc')
In order to get a single string of all permutation strings separated by new-line characters, simply call '\n'.joinwith the output of that function. For example,
为了获得由换行符分隔的所有置换字符串的单个字符串，只需调用'\n'.join该函数的输出即可。例如，
string = '\n'.join(Permute('abc'))
By the way, the printresults for the two options above are identical.
顺便说一下，上述print两个选项的结果是相同的。
回答by Adrian Ratnapala
This kind of thing is a nice place for generators (https://docs.python.org/3.3/tutorial/classes.html#generators), and yield.
这种事情是生成器的好地方（https://docs.python.org/3.3/tutorial/classes.html#generators），并且yield.
Try something like this (not tested):
尝试这样的事情（未测试）：
def permute_string(s):
if len(s) <= 1: # "" and 1 char strings are their all their own permutaions.
yield s
return
head = s[0] # we hold on to the first character
for tail in permute_string(s[1:]) : # permute the rest
yield head + tail
# main
for permutation in permute_string(s) :
print(permutation)
This is the classic permutation algorithm: you keep the first character and prepend it to all permutations of the remaining characters. This particular function is a python generator: that means it can keep running while yielding its results one-by-one. In this case, it makes it easier to concentrate on the algorithm without worrying about the details of how to get the data back to the caller.
这是经典的排列算法：保留第一个字符并将其添加到其余字符的所有排列之前。这个特殊的函数是一个 python 生成器：这意味着它可以继续运行，同时一个一个地产生结果。在这种情况下，可以更轻松地专注于算法，而不必担心如何将数据返回给调用者的细节。
回答by Brent Douglas
Not sure about efficiency but this should work too.
不确定效率，但这也应该有效。
def find_permutations(v):
if len(v) > 1:
for i in perms(v):
nv = i[1:]
for j in perms(nv):
print(i[0] + j)
else:
print(v)
def perms(v):
if not hasattr(perms, 'original'):
perms.original = v
perms.list = []
nv = v[1:] + v[0]
perms.list.append(nv)
if perms.original == nv:
l = perms.list
del perms.original
del perms.list
return l
return perms(nv)
find_permutations('abc')
回答by karakfa
The result of permutations will be a collection, let's say a list. It will make your code cleaner if you think this way and if required you can join the results into a single string. A simple example will be
排列的结果将是一个集合，比如说一个列表。如果您以这种方式思考，它将使您的代码更清晰，并且如果需要，您可以将结果连接到一个字符串中。一个简单的例子是
def perms(s):
if(len(s)==1): return [s]
result=[]
for i,v in enumerate(s):
result += [v+p for p in perms(s[:i]+s[i+1:])]
return result
perms('abc')
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
print('\n'.join(perms('abc')))
abc
acb
bac
bca
cab
cba
回答by apoorva R
Here is the code:
这是代码：
def fperms(elements):
if len(elements)<=1:
yield elements
else:
for p in fperms(elements[1:]):
for i in range(len(elements)):
yield p[:i]+elements[0:1]+p[i:]
