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? — ouroboros1
– ouroboros1, Commented May 27, 2022 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 the behaviour of the code. — Karl Knechtel
– Karl Knechtel, Commented May 27, 2022 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
– Karl Knechtel, Commented May 27, 2022 at 22:08

Karl Knechtel · Accepted Answer · 2022-05-27 22:09:04Z

3

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)

edited May 27, 2022 at 22:09

Karl Knechtel

61.4k14 gold badges131 silver badges193 bronze badges

answered May 27, 2022 at 21:57

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

AboAmmar · Accepted Answer · 2022-05-27 23:15:39Z

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

Collectives™ on Stack Overflow

Permutations of Array - Python

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related