All Permutations of a String in Python (Recursive)

Question

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!

That function is recursive and iterative. I think you want to just prepend s[0] to the recursion on s[1:] without the loop. — kojiro
– kojiro, Commented Apr 16, 2014 at 18:14
@squiguy: At a guess, I think gnp210 is trying to learn stuff. And the best way to learn is to do. — Adrian Ratnapala
– Adrian Ratnapala, Commented Apr 16, 2014 at 18:51

karakfa · Accepted Answer · 2016-01-05 20:20:57Z

15

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

edited Jan 5, 2016 at 20:20

answered Jan 5, 2016 at 20:09

karakfa

67.8k8 gold badges45 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Jay Taylor Over a year ago

Thanks @karakfa, this is the cleanest and easiest to understand recursive permutation implementation I've seen for python!

Sotirios Delimanolis · Accepted Answer · 2016-06-21 19:05:12Z

13

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.

edited Jun 21, 2016 at 19:05

Sotirios Delimanolis

281k62 gold badges718 silver badges744 bronze badges

answered Apr 16, 2014 at 18:31

barak manos

30.3k10 gold badges67 silver badges117 bronze badges

22 Comments

barak manos Over a year ago

@gnp210: Oh, OK, I get it. Then you should simply call '\n'.join(Permute('abc')). I will add it to the answer.

barak manos Over a year ago

@gnp210: A recursive function "tends" to perform the same thing many times, due to its nature of calling itself. Now, since it builds up the final output from partial outputs, the final output is only available to you outside the function (where you call it). Assuming that you do not want to print all the partial outputs that are generated during the process, you should call print only outside the recursive function!!!

Jossie Calderon Over a year ago

Suppose I have the str = 'h'. prevList returns []. nextList returns []. Both have length 0. Therefore, the permutation set returns [].

user000001 Over a year ago

Meta discussion about this answer: meta.stackoverflow.com/questions/326544/…

barak manos Over a year ago

@user000001: Thank you very much for pointing this out. Not only did that user make this false comment about my answer (see comment thread above), but he also posted that false comment, excusing his action, on this other forum. I will make sure to add this comment thread there too. Thanks again :)

|

S.A. · Accepted Answer · 2017-10-25 07:36:23Z

2

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

edited Oct 25, 2017 at 7:36

S.A.

2,1911 gold badge26 silver badges40 bronze badges

answered Oct 17, 2016 at 10:20

apoorva R

213 bronze badges

Comments

Brent Douglas · Accepted Answer · 2016-01-05 19:16:36Z

0

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

edited Jan 5, 2016 at 19:16

answered Jan 5, 2016 at 19:08

Brent Douglas

416 bronze badges

Comments

Athena · Accepted Answer · 2021-11-11 08:02:30Z

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

answered Nov 11, 2021 at 8:02

Athena

1

1 Comment

holydragon Over a year ago

The answer would be more useful if you can add some explanation along with the code.

Adrian Ratnapala · Accepted Answer · 2014-04-17 06:30:40Z

-3

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.

edited Apr 17, 2014 at 6:30

answered Apr 16, 2014 at 18:49

Adrian Ratnapala

5,8032 gold badges31 silver badges39 bronze badges

2 Comments

gnp210 Over a year ago

This one gives a list out of bound exception in the for-loop once s reaches a size of 1. I tried putting the for loop inside of an else statement, but then the function only returns "abc"

Adrian Ratnapala Over a year ago

The bugs were that the (a) function tried to keep going even after yielding it's one-and-only result and (b) I used < 1 when I meant <= 1. I have fixed both these problems in the example.

Collectives™ on Stack Overflow

All Permutations of a String in Python (Recursive)

6 Answers 6

1 Comment

22 Comments

Comments

Comments

1 Comment

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

1 Comment

22 Comments

Comments

Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related