Hướng dẫn permutation string python

I need a kick in the head on this one. I have the following recursive function defined:

Nội dung chính

• Not the answer you're looking for? Browse other questions tagged python recursion permutation or ask your own question.
• How do you find the permutation of a string in Python?
• How do you do permutations in Python?
• How do you find the permutation of a string?
• Is there a permutation function in Python?

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!

asked Apr 16, 2014 at 18:04

gnp210gnp210

1531 gold badge1 silver badge9 bronze badges

3

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

answered Jan 5, 2016 at 20:09

karakfakarakfa

65k7 gold badges38 silver badges55 bronze badges

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.

answered Apr 16, 2014 at 18:31

barak manosbarak manos

28.9k9 gold badges57 silver badges113 bronze badges

22

Here is the code:

def fperms[elements]:
    if len[elements] 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']

answered Jan 5, 2016 at 19:08

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

answered Nov 11, 2021 at 8:02

1

This kind of thing is a nice place for generators [//docs.python.org/3.3/tutorial/classes.html#generators], and yield.

Try something like this [not tested]:

def permute_string[s]:
    if len[s]