Permutations of Array - Python

Question

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!

Does this answer your question? [How to generate all permutations of a list?](https://stackoverflow.com/questions/104420/how-to-generate-all-permutations-of-a-list) — ouroboros1, May 27 '22 at 21:52
Will you be satisfied by using the built-in standard library tools for this? Or is the question specifically about fixing the code and understanding the problem? In the latter case, it would help to explain *what goes wrong* with this code. What output do you get, and how does it appear to differ, conceptually, from the correct output? Also, try to find the problem yourself first, by [properly studying](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) the behaviour of the code. — Karl Knechtel, May 27 '22 at 22:06
To save you some time, though: try to think carefully about the line `permutation = permutation_of_all_chars_except_last.insert(position, last_char)`. What do you expect will happen to the list as a result? What do you expect to be assigned to `permutation`? Now, *check that*, and also *read the documentation* for `list.insert` to understand what is happening. It **does not** mean "create a new list with an extra value in the specified position, and return that new list". It means "modify the existing list by putting another value in it, and return `None`." — Karl Knechtel, May 27 '22 at 22:08

score 3 · Answer 1 · edited May 27 '22 at 22:09

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)

score 1 · Answer 2 · answered May 27 '22 at 23:15

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

Permutations of Array - Python

2 Answers2