#### Jay Taylor's notes

back to listing index

### All Permutations of a String in Python (Recursive)

[web search]
Original source (stackoverflow.com)
Clipped on: 2016-07-27

5,473 43056

Dismiss
Announcing Stack Overflow Documentation

We started with Q&A. Technical documentation is next, and we need your help.

Whether you're a beginner or an experienced developer, you can contribute.

I want to help →

# 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!

 asked Apr 16 '14 at 18:04 gnp210 5316
 3 upvote flag
Have you considered using `itertools.permutations`? – squiguy Apr 16 '14 at 18:04
 1 upvote flag
That function is recursive and iterative. I think you want to just prepend `s` to the recursion on `s[1:]` without the loop. – kojiro Apr 16 '14 at 18:14
 1 upvote flag
@squiguy: At a guess, I think gnp210 is trying to learn stuff. And the best way to learn is to do. – Adrian Ratnapala Apr 16 '14 at 18:51

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

 Sotirios Delimanolis 149k22215333 answered Apr 16 '14 at 18:31 barak manos 19.8k32255
 upvote flag
I am looking to return a string, not a list. Can you see where in my code I am going wrong? – gnp210 Apr 16 '14 at 19:16
 1 upvote flag
@gnp210: Oh, OK, I get it. Then you should simply call `'\n'.join(Permute('abc'))`. I will add it to the answer. – barak manos Apr 16 '14 at 19:43
 1 upvote flag
Suppose I have the str = 'h'. prevList returns []. nextList returns []. Both have length 0. Therefore, the permutation set returns []. – Jossie Calderon Jun 21 at 0:10
 1 upvote flag
 1 upvote flag
@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 :) – barak manos Jun 21 at 13:25

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 at 20:09 karakfa 20k31231
Thanks @karakfa, this is the cleanest and easiest to understand recursive permutation implementation I've seen for python! – Jay Taylor Jun 29 at 0:07

I think you can use this logic:

helper function

``````def toString(List):
return ''.join(List)

# Function to print permutations of string
# This function takes three parameters:
# 1. String
# 2. Starting index of the string
# 3. Ending index of the string.
def permute(a, l, r):
if l==r:
print toString(a)
else:
for i in xrange(l,r+1):
a[l], a[i] = a[i], a[l]
permute(a, l+1, r)
a[l], a[i] = a[i], a[l] ``````

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 + j)
else:
print(v)

def perms(v):
if not hasattr(perms, 'original'):
perms.original = v
perms.list = []
nv = v[1:] + v
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')``````

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 # we hold on to the first character
for tail in permute_string(s[1:]) :   # permute the rest

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

 upvote flag
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" – gnp210 Apr 16 '14 at 21:38
 upvote flag
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. – Adrian Ratnapala Apr 17 '14 at 6:31

community wiki

## Not the answer you're looking for? Browse other questions tagged pythonrecursionpermutation or ask your own question.

 asked 2 years ago viewed 8439 times active 23 days ago
Featured on Meta

Hot Meta Posts

Get the weekly newsletter! In it, you'll get:

• The week's top questions and answers
• Important community announcements 