Python recursion permutations

Question

Im having trouble trying to make a permutation code with recursion. This is suppose to return a list back to the use with all the posible position for each letter. so for the word cat it is suppose to return ['cat','act',atc,'cta','tca','tac'] . so far i have this

def permutations(s):
    lst=[]
    if len(s) == 1 or len(s) == 0 :
        # Return a list containing the string, not the string
        return [s]
    # Call permutations to get the permutations that don't include the
    # first character of s
    plst = permutations(s[1:])
    print(plst)
    for item in plst:
        print (item)
        plst= permutations(s[1+1:])

         # Now move through each possible position of the first character
        # and create a new string that puts that character into the strings
        # in plst
        for i in range(len(s)):
            pass
            # Create a new string out of item
            # and put it into lst
        # Modify
    for item in lst:
        print(index)

There are steps there but im not sure how to use them

Answer 1

You want to do recursion, so you first have to find out how the recursion would work. In this case it is the following:

permutation [a,b,c,...] = [a + permutation[b,c,...], b + permutation[a,c,..], ...]

And as a final condition:

permutation [a] = [a]

So the recursion splits up the list in sublists with one element extracted each time. Then this element is added to the front of each of the permutations of the sublist.

So in pseudo-code:

def permutation(s):
   if len(s) == 1:
     return [s]

   perm_list = [] # resulting list
   for a in s:
     remaining_elements = [x for x in s if x != a]
     z = permutation(remaining_elements) # permutations of sublist

     for t in z:
       perm_list.append([a] + t)

   return perm_list

Does this help?