Python Forum

Hello,

I need to implement a function that accepts an input of a list and return the sorted version of this list after generating all possible permutations
e.g.:

3, 7, 1
its permutations are:
1, 3, 7
1, 7, 3
3, 7, 1
3, 1, 7
7, 1, 3
7, 3, 1

I managed to write a recursive function to generate these permutations but I want this function to output (1, 3, 7) only how can I do this?

arr = [7, 1, 3]
sortedList = arr
def permutationSort(arr, flag, p, ):
    if len(arr) == len(p):
        print(p) #here I can see that I can get all permutations
        global sortedList
        if p < sortedList:
            sortedList = p


    for i in range(len(arr)):
        if flag[i] == 1:
            continue
        else:
            flag[i] = 1
            p.append(arr[i])
            permutationSort(arr, flag, p)
            p.pop()
            flag[i] = 0

permutationSort(arr, [0]*(len(arr)), [])
print(sortedList) #this is not the correct answer

You haven't written a function to generate the permutations. You've written a function to show the permutations. The function returns nothing (or rather, None). The reason you are getting an empty list at the end is that you are assigning p to sortedList. But p is a list, which is a mutable data type. So when you change p, you change sortedList as well. Then you go on to do a bunch of appends and pops to p, which is where I'm guessing it gets emptied.

Don't use global. Use the return statement to return values from your functions. Your recursive function should return a list of permutations. When it gets to the bottom of the recursion, it should return a list containing the permutation it found, with the permutation protected from mutability (either by copying with [:] or making immutable with tuple()). That is return to the next level, where it is extended on to the list that level is returning. Then at the top you will return a full list of permutations that you can sort