Python中字符串的所有排列(递归)

Question

我需要在这个头上踢一脚.我定义了以下递归函数:

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")目前返回:

abccb
bacca
cabba

期望的结果是

abc
acd
bac
bca
cab
cba

我在哪里错了？我怎样才能想出这个解决方案呢？

注意:我知道itertools函数.我试图了解如何为我自己的学习递归地实现排列.这就是为什么我希望有人指出我的代码有什么问题,以及如何以不同的方式来解决它.谢谢!

Answer 1

你去(递归排列):

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

要获取所有排列字符串的列表,只需使用输入字符串调用上面的函数即可.例如,

stringList = Permute('abc')

为了获得由换行符分隔的所有排列字符串的单个字符串,只需'\n'.join使用该函数的输出调用即可.例如,

string = '\n'.join(Permute('abc'))

顺便说一下,print上面两个选项的结果是相同的.

Answer 2

排列的结果将是一个集合,让我们说一个列表.如果您这样想,它将使您的代码更清晰,如果需要,您可以将结果加入到单个字符串中.一个简单的例子就是

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