12

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!

3
  • 3
    Have you considered using itertools.permutations?
    – squiguy
    Apr 16, 2014 at 18:04
  • 1
    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, 2014 at 18:14
  • 1
    @squiguy: At a guess, I think gnp210 is trying to learn stuff. And the best way to learn is to do. Apr 16, 2014 at 18:51

6 Answers 6

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

22
  • 1
    @gnp210: Oh, OK, I get it. Then you should simply call '\n'.join(Permute('abc')). I will add it to the answer. Apr 16, 2014 at 19:43
  • 1
    @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!!! Apr 16, 2014 at 21:24
  • 1
    Suppose I have the str = 'h'. prevList returns []. nextList returns []. Both have length 0. Therefore, the permutation set returns []. Jun 21, 2016 at 0:10
  • 1
    Meta discussion about this answer: meta.stackoverflow.com/questions/326544/…
    – user000001
    Jun 21, 2016 at 13:06
  • 1
    @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 :) Jun 21, 2016 at 13:25
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:]
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')
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))
1
  • 1
    The answer would be more useful if you can add some explanation along with the code.
    – holydragon
    Nov 11, 2021 at 10:19
-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.

2
  • 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, 2014 at 21:38
  • 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. Apr 17, 2014 at 6:31

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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