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

12 投票
6 回答
35598 浏览
提问于 2025-04-18 03:01

我在这个问题上需要一些帮助。我定义了一个递归函数:

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这个函数。我想理解如何递归地实现排列组合,以便自己学习。这就是为什么我希望有人能指出我代码中的问题,以及如何换个思路来解决它。谢谢!

6 个回答

0

这段代码是用来处理一些数据的。它可能会从某个地方获取信息,然后对这些信息进行一些操作,比如计算、筛选或者格式化。具体来说,代码块中的内容会告诉计算机该怎么做,如何把输入的数据变成我们想要的结果。

在编程中,代码就像是给计算机下达的指令,告诉它要完成什么任务。即使你现在对这些代码不太理解,但只要你慢慢学习,就会明白每一行代码的作用。

总之,这段代码的目的是为了让计算机处理数据,最终得到我们需要的结果。

def get_permutations(sequence):
    if len(sequence) == 1:
        return [sequence]  # base case
    else:
        result = []
        for letter in sequence:
            result += [letter +
                    other_letter for other_letter in get_permutations(sequence.replace(letter, ""))]


 test_1 = 'abc'
print("Input: ", test_1)
print("Expected output: ", ['abc', 'acb', 'bac', 'bca', 'cab', 'cba'])
print("Actual output: ", get_permutations(test_1))
0

我不太确定这个方法的效率怎么样,但这个方法也应该能奏效。

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')
2

这里是代码:

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:]
13

这里有一个(递归排列)的方法:

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 结果是一样的。

15

排列的结果会是一个集合,我们可以把它称作一个列表。如果你这样想的话,你的代码会更简洁。如果需要的话,你可以把这些结果合并成一个字符串。下面是一个简单的例子:

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

撰写回答