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:
        yield elements
    else:
        for p in fperms(elements[1:]):
            for i in range(len(elements)):
                yield p[:i]+elements[0:1]+p[i:]

S.A.

1,6091 gold badge21 silver badges37 bronze badges

answered Oct 17, 2016 at 10:20

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

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 (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.

answered Apr 16, 2014 at 18:49

Adrian RatnapalaAdrian Ratnapala

5,3171 gold badge28 silver badges39 bronze badges

2

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?

Procedure To Find The Permutation Of A String.

Import the itertools module..

Initialize the string..

Use the itertools. permutations method to find the permutation of the string..

In the third step, the method returns an object and convert it into a list. List contains a permutation of string as tuples..

How do you do permutations in Python?

The number of permutations on a set of n elements is given by n!. For example, there are 2! = 2*1 = 2 permutations of {1, 2}, namely {1, 2} and {2, 1}, and 3! = 3*2*1 = 6 permutations of {1, 2, 3}, namely {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2} and {3, 2, 1}.

How do you find the permutation of a string?

We can find the count without finding all permutation. Idea is to find all the characters that is getting repeated, i.e., frequency of all the character. Then, we divide the factorial of the length of string by multiplication of factorial of frequency of characters.

Is there a permutation function in Python?

To calculate permutations in Python, use the itertools. permutation() method. The itertools. permutations() method takes a list, dictionary, tuple, or other iterators as a parameter and returns the permutations of that list.