Using recursion for permutations of a list

Question

So been struggling with this one, I'm close and have finally found a way to somewhat desired output now repeats in generated list.

input['a','r','t']

def permutations(string_list):

    if len(string_list) <= 1:
        return [string_list]

    perm_list = []
    for letter_index in range(len(string_list)):
        perms_1 = string_list[letter_index]
        rest = string_list[:letter_index] + string_list[letter_index + 1:]
        for perms_2 in permutations(rest):
            perm_list.append([perms_1] + perms_2)

    return perm_list

output

[[['a', 'r', 't'], ['a', 't', 'r'], ['r', 'a', 't'], ['r', 't', 'a'],
  ['t', 'a', 'r'], ['t', 'r', 'a']], [['a', 'r', 't'], ['a', 't', 'r'],
  ['r', 'a', 't'],
.........repeats.......repeats..
..for quite sometime but not infinite....]]]

DESIRED output

[['a', 'r', 't'], ['a', 't', 'r'], ['r', 'a', 't'], ['r', 't', 'a'],
 ['t', 'a', 'r'], ['t', 'r', 'a']]

so it's permutation but what is tripping me up is having to use the list of strings and outputting a list of lists of strings. I have redone this multiple time and have the basis of recursive permutations down if I was just using a string 'art' as input or having a list output ['art','atr','rat',ect..] just not sure where I am going wrong. No import of itertools allowed and really wish I didn't need for loops but using comprehension recursion call gives me same results...any help or pointers appreciated. Not looking for just a redo I want to understand....

Have you considered Heap's algorithm? See https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations. — Mario Camilleri, Mar 15 '19 at 16:35
PS. your program ran correctly for me - it did not repeat after generating all permutations of the input list. — Mario Camilleri, Mar 15 '19 at 16:40
ahh i was calling the recursive function to separate 'art' as ['a','r','t'] prior to inputting it into the recursive function....found my error... — Excubi, Mar 15 '19 at 17:45

score 0 · Answer 1 · answered Mar 15 '19 at 16:37

Using this, you get the desired output:

from itertools import permutations

inp = ['a', 'r', 't']

list(permutations(inp, 3))

Out:

[('a', 'r', 't'),
 ('a', 't', 'r'),
 ('r', 'a', 't'),
 ('r', 't', 'a'),
 ('t', 'a', 'r'),
 ('t', 'r', 'a')]

The result is a list of tuples, but you can convert them to lists if you want.

score 0 · Answer 2 · answered Mar 15 '19 at 16:41

def permute(input, l, r, arr = []):
    if l == r:
        arr.append(input)
    else:
        for i in range(l, r + 1):
            input[l], input[i] = input[i], input[l]
            permute(input, l + 1, r, arr)
            input[l], input[i] = input[i], input[l]

    return arr

input = ['a','r','t']
n = len(input)
print (permute(input, 0, n - 1))

result:

[['a', 'r', 't'], ['a', 'r', 't'], ['a', 'r', 't'], ['a', 'r', 't'], ['a', 'r', 't'], ['a', 'r', 't']]

NOTE: You are missing else statement

How did i miss that....hours of it not seeing that....gragrghghghgghg...thanks....wow — Excubi, Mar 15 '19 at 17:25

Using recursion for permutations of a list

2 Answers2