Python recursion permutations

Question

I'm having trouble trying to make a permutation code with recursion. This is suppose to return a list back to the use with all the possible position for each letter.

For the word cat, it is suppose to return ['cat','act',atc,'cta','tca','tac'].

So far I have this code:

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?

Answer 2

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

You can use a function that iterates an index through the list, and yield a list consisting of the value at the index followed by the permutations of the rest of the list values. Below is an example using features from Python 3.5+:

def permutations(s):
    if not s:
        yield []
    yield from ([s[i], *p] for i in range(len(s)) for p in permutations(s[:i] + s[i + 1:]))

so that list(permutations('abc')) returns:

[['a', 'b', 'c'],
 ['a', 'c', 'b'],
 ['b', 'a', 'c'],
 ['b', 'c', 'a'],
 ['c', 'a', 'b'],
 ['c', 'b', 'a']]

Answer 5

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

Answer 7

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 8

The easiest way to do permutations through recursion is to first imagine a recursion tree for the problem

base case: if we are given an empty list permutation would be [ [] ] Then we just want to remove an item from the list and add it to all indices of the rest of the list.

eg input : [a,b,c]
first = a
rest = [b,c]
all = [a,b,c] , [b,a,c] , [b,c,a]

Time: O(N!) #This is best since we are creating N! element
Space O(N^2) #N stack frame * N item in per_with_all

Source: https://www.youtube.com/watch?v=us0cYQXQpxg

def permetutation(arr):
    if len(arr) == 0:
        return [ [] ]
    #We remove 1st item from error as at each level we introduce 1 item 
    first_elenment = arr.pop(0)

    #getting permet for all other item 
    perm_without_first = permetutation(arr)

    per_with_all = []

    #Add permtution to every index 
    for comb in perm_without_first:
        for ind in range(len(comb)+1): #We also wan to add elenment to last so do +1 
            all = comb[0:ind] + [first_elenment] + comb[ind:] 
            per_with_all.append( all)

    return per_with_all

Answer 9

These examples codes are really helpful but I found a test case failed when I was doing a code practice on CodeSignal. basically all the given approach here ignoring if there are any duplicates.

Input: s: "ABA" 
Output: ["ABA", "AAB", "BAA", "BAA", "AAB", "ABA"] 
Expected Output: ["AAB", "ABA", "BAA"]

So, if you see, it has following duplicates in the output:

["BAA", "AAB", "ABA"]

I modified this by bit here

def stringPermutations(s):
        news = s
        if len(news) == 1:
            return [news]
        res = []
        for permutation in stringPermutations(news[1:]):
            for i in range(len(news)):
                res.append(permutation[:i] + news[0:1] + permutation[i:])
        # To Remove Duplicates From a Python List: list(dict.fromkeys(res))
        # To Sort List : sorted()
        return sorted(list(dict.fromkeys(res)))

def main():
    arr = 'ABA'
    print(stringPermutations(arr))

if __name__ == '__main__':
    main()

But this answer is not appropriate as per time complexity. Time complexity with this approach is: o(n^2)

I think the below approach is quite reasonable.

def stringPermutations(string, prefix, permutation_list):
    #Edge case check
    if len(string) == 0:
        permutation_list.append(prefix)
    else:
        for i in range(len(string)):
            rem = string[0:i] + string[i + 1:]
            stringPermutations(rem, prefix + string[i], permutation_list)
    return sorted(list(dict.fromkeys(permutation_list)))
def main():
    permutation_list = []
    print(stringPermutations('aba','', permutation_list))

if __name__ == '__main__':
    main()

Answer 10

def permute(s):
    ch = list(s)
    if len(ch) == 2:
        per = ch[1] + ch[0] 
        return [''.join(ch)] + [per]
    if len(ch) < 2:
        return ch
    else:
        return [ init+per for init in ch for per in permute(''.join(ch).replace(init,""))] 

Answer 11

Using generators:

def generate_perm(alist, index, path, result):
    yield path
    for i in range(index, len(alist)):
        yield from generate_perm(alist, i + 1, path + [alist[index]], result)


print(list(generate_perm([0, 1, 2], 0, [], []))

Answer 12

Too late, but this one should also answer your question :)

def permutation(sofar, rest,res):
    if len(rest) == 0:
        res.add(sofar)
    else:
        for i in range(len(rest)):
            permutation(sofar + rest[i], rest[:i] + rest[i+1:len(rest)], res)
    return res

s = 'cat'
res = set()
permutation('',s,res)
print(res)

Answer 13

Solution with recursion

Libraries aren't needed but wants it much simpler

import random  
import string 
import math

def perm(string, output = []):
strlen = len(string)
strlist = list(string)
if (len(output) == (math.factorial(strlen))):
  return output

elif string in output:
  string = (''.join((random.sample(strlist, 3))))
  return perm(string, output)

else:
  output.append(string)
  string = (''.join((random.sample(strlist, 3))))
  return perm(string, output)

Answer 14

you can solve the problem as following:

def permutations (arr):
    if arr == []:
        return [ "" ]
    res = []
    for i in range (len(arr)):
        l = remove(arr,i)
        for j in perm(l):
            res.append(arr[i] + str(j))
    return res

def remove (l, index):
    res = []
    for i in range (len(l)):
        if i == index:
            continue
        res.append(l[i])
    return res

the permutations function does the following: 1 - if the input is empty then we do not have any permutations instead of the empty string so the result will be [ "" ]. This is the base of the recursive function. 2 - otherwise, note that in a permutation each element can occur as the first element. Using this logic, the permutations function takes each element from the array and sets it as the first element of the resulting permutation (this is the outer loop). this element is added to all the permutations of the remaining elements (If you use a pen and paper and walk through the procedure of the function step by step it will be much easier to understand).

The remove function takes a list and an index and returns a new list without the element in that index.

Obviously many approaches exist. This approach only uses the minimum python methods and I consider it a beginner friendly and easy-to-understand approach. However it is not the most efficient!

Test it with the following and you will get the desired output.

print (permutations("cat"))