I am trying to get all of the permutations of an input array and for some reason cannot get the right answer no matter how hard I try. Below is a sample input

Input: array = [1, 2, 3]

Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

I am trying to do this recursively by going all the way down to the base case of there only being one element. Then I am going to add one element at a time and put it in every possible position of the array. Below is my recursive attempt

def get_permutations(array):
    # Base case
    if len(array) <= 1:
        return [array]

    all_chars_except_last = array[:-1]
    last_char = array[-1]

    permutations_of_all_char_except_last = get_permutations(all_chars_except_last)

    # Put the last char in all possible positions for each of the above permutations
    permutations = []
    for permutation_of_all_chars_except_last in permutations_of_all_char_except_last:
        for position in range(len(all_chars_except_last) 1):
            permutation = permutation_of_all_chars_except_last.insert(position, last_char)
        
            permutations.append(permutation)
    return permutations

Advice as to where my code is going would be very much appreciated! I am just trying to increase my skills in this wonderful world that is coding!

CodePudding user response：

The problem with your code is that the insert method does not return the list, but None. Moreover, insert mutates the list you call it on, which is undesired also.

So you need to replace that statement with a statement that creates a new list without mutating the original:

permutation = permutation_of_all_chars_except_last[:position]   [last_char]   permutation_of_all_chars_except_last[position:]

Or, alternatively, first take a copy and then call insert:

permutation = permutation_of_all_chars_except_last[:]
permutation.insert(position, last_char)

CodePudding user response：

Since you are doing this for learning purposes and to increase your skills in coding, I'm adding other implementations based on generators. The problem with most traditional recursive implementations is that it can eat up all your memory quite fast with increasing array length.

def get_permutations(array):
    if len(array) <= 1:
        yield array
    else:
        for perm in get_permutations(array[1:]):
            for i in range(len(array)):
                yield perm[:i]   array[0:1]   perm[i:]

The permutation arrays will get materialized at the moment of consumption, so memory will be preserved.

list(get_permutations([1,2,3]))
# [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]

Moreover, efficient implementations exist in modules like ietrtools:

import itertools as it
list(it.permutations([1, 2, 3]))
# [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]