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

This is the easiest solution I came up with.

   def permutations(_string):
        # stores all generated permutations
        permutations = []

        # this function will do recursion
        def step(done, remain):
            # done is the part we consider "permutated"
            # remain is the set of characters we will use

            # if there is nothing left we can appened generated string
            if remain == '':
                permutations.append(done)
            else:

                # we iterate over the remaining part and indexing each character
                for i, char in enumerate(remain):
                    # we dont want to repeat occurance of any character so pick the remaining
                    # part minus the currect character we use in the loop
                    rest = remain[:i] + remain[i + 1:]
                    # use recursion, add the currect character to done part and mark rest as remaining
                    step(done + char, rest)
        step("", _string)
        return permutations

You can test it with:

@pytest.mark.parametrize('_string,perms', (
    ("a", ["a"]),
    ("ab", ["ab", "ba"]),
    ("abc", ["abc", "acb", "cba", "cab", "bac", "bca"]),
    ("cbd", ["cbd", "cdb", "bcd", "bdc", "dcb", "dbc"])
))
def test_string_permutations(_string, perms):
    assert set(permutations(_string)) == set(perms)

Answer 2

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?

Answer 3

When you're lost in recursive function, you should draw the call tree. The following version (inspired @Ben answer) keep the input order (if the input is in lexicographic order, the list of permutations will be, '012' -> ['012', '021', '102', '120', '201', '210'].

def permut2(mystr):
    if len(mystr) <= 1:
        return [mystr]
    res = []
    for elt in mystr:
        permutations = permut2(mystr.replace(elt, ""))
        for permutation in permutations:
            res.append(elt + permutation)
    return res

The following version works for strings and lists, notice the reconstruction step is not the same:

def permut(array):
    if len(array) == 1:
        return [array]
    res = []
    for permutation in permut(array[1:]):
        for i in range(len(array)):
            res.append(permutation[:i] + array[0:1] + permutation[i:])
    return res

As an exercice, you should draw call tree of the these functions, do you notice something ?

Answer 4

I know this is a me too, but I think this one might be easier for some folks to understand....

1. The base case is when the input is just one character.
2. Setup up a for loop that iterates through each of the letters in the string.
3. Another for loop recursively permutes through all the other possibilities.

def permute(s):

out = []

if len(s) == 1:
    out = [s]
else:
    for i,let in enumerate(s):
        for perm in permute(s[:i]+s[i+1:]):
            out += [let+perm]
return out

Answer 5

Recursively, think about the base case and build from that intuition.

1) What happens when there's only one character 'c'? There's only one permutation of that element, and so we return a list containing only that element.

2) How can we generate the next permutation given the last one? Adding an additional letter 'a' at all possible positions in the previous permutation 'c' gives us 'ca', 'ac'.

3) We can continue building larger and larger permutations by adding an additional character at all possible positions in each earlier permutation.

The following code returns a list of one character if the string has one character or less. Otherwise, for all permutations not including the last character in the string s[-1], we generate a new string for each position where we could include that character and append the new string to our current list of permutations.

def permutations(s):
    if len(s) <= 1:
        return [s]
    else:
        perms = []
        for e in permutations(s[:-1]):
            for i in xrange(len(e)+1):
                perms.append(e[:i] + s[-1] + e[i:])
        return perms

Answer 6

def permutations(string_input, array, fixed_value=""):
    for ch in string_input:
        permutations(string_input.replace(ch, ""), array, fixed_value + ch)
    if not string_input:
        array.append(fixed_value)

You can call it by

array = []
permutations("cat", array)
print array