back to listing index

All Permutations of a String in Python (Recursive)

[web search]
Original source (stackoverflow.com)
Tags: python algorithms permutations recursion
Clipped on: 2016-07-27

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 →

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
Image (Asset 2/8) alt=
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[0] 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[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 '14 at 18:31
Image (Asset 4/8) alt=
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
Image (Asset 5/8) alt=
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] 
answered Jul 1 at 6:58
Image (Asset 6/8) alt=

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 at 19:08
Image (Asset 7/8) alt=

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 '14 at 18:49
Image (Asset 8/8) alt=
Adrian Ratnapala
2,9091325
   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

Your Answer

asked

2 years ago

viewed

8439 times

active

23 days ago

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

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

Hot Network Questions

Technology Life / Arts Culture / Recreation Science Other
  1. Stack Overflow
  2. Server Fault
  3. Super User
  4. Web Applications
  5. Ask Ubuntu
  6. Webmasters
  7. Game Development
  8. TeX - LaTeX
  1. Programmers
  2. Unix & Linux
  3. Ask Different (Apple)
  4. WordPress Development
  5. Geographic Information Systems
  6. Electrical Engineering
  7. Android Enthusiasts
  8. Information Security
  1. Database Administrators
  2. Drupal Answers
  3. SharePoint
  4. User Experience
  5. Mathematica
  6. Salesforce
  7. ExpressionEngine® Answers
  8. more (13)
  1. Photography
  2. Science Fiction & Fantasy
  3. Graphic Design
  4. Movies & TV
  5. Seasoned Advice (cooking)
  6. Home Improvement
  7. Personal Finance & Money
  8. Academia
  9. more (9)
  1. English Language & Usage
  2. Skeptics
  3. Mi Yodeya (Judaism)
  4. Travel
  5. Christianity
  6. Arqade (gaming)
  7. Bicycles
  8. Role-playing Games
  9. more (21)
  1. Mathematics
  2. Cross Validated (stats)
  3. Theoretical Computer Science
  4. Physics
  5. MathOverflow
  6. Chemistry
  7. Biology
  8. more (5)
  1. Stack Apps
  2. Meta Stack Exchange
  3. Area 51
  4. Stack Overflow Careers
site design / logo © 2016 Stack Exchange Inc; user contributions licensed under cc by-sa 3.0 with attribution required
rev 2016.7.25.3833