All Permutations of a String in Python (Recursive)

问题:

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:

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!

回答1:

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'.join with the output of that function. For example,

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

By the way, the print results for the two options above are identical.

回答2:

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

回答3:

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

回答4:

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

回答5:

This kind of thing is a nice place for generators (https://docs.python.org/3.3/tutorial/classes.html#generators), and 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.