How to fix method in python that returns a 2d array with empty array elements?

Question

The following code implements a backtracking algorithm to find all the possible permutations of a given array of numbers and the record variable stores the permutation when the code reaches base case. The code seems to run accordingly, that is, the record variable gets filled up with valid permutations, but for some reason when the method finishes the method returns a two-dimensional array whose elements are empty.

I tried declaring record as a tuple or a dictionary and tried using global and nonlocal variables, but it none of it worked.

def permute(arr):
    record = []
    def createPermutations(currentArr, optionArr):
        if len(optionArr) == 0:
            if len(currentArr) != 0: record.append(currentArr)
            else: pass
            print(record)
        else:
            for num in range(len(optionArr)):
                currentArr.append(optionArr[num])
                option = optionArr[0:num] + optionArr[num+1::]
                createPermutations(currentArr, option)
                currentArr.pop()

    createPermutations([], arr)
    return record

print(permute([1,2,3]))

The expect result should be [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]], but instead I got [[], [], [], [], [], []].

Answer 1

With recursive functions, you should pass a copy of the current array, rather than having all of those currentArr.pop() mutating the same array.

Replace

createPermutations(currentArr, option)

by

createPermutations(currentArr[:], option)

Finally, as a learning exercise for recursion, something like this is fine, but if you need permutations for a practical programming problem, use itertools:

print([list(p) for p in itertools.permutations([1,2,3])])

Answer 2

I would accept John Coleman's answer as it is the correct way to solve your issue and resolves other bugs that you run into as a result.

The reason you run into this issue because python is pass-by-object-reference, in which copies of lists are not passed in but the actual list itself. What this leads to is another issue in your code; in which you would get [[3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]] as your output when you print(record).

Why this happens is that when you call record.append(currentArr), it actually points to the same object reference as all the other times you call record.append(currentArr). Thus you will end up with 6 copies of the same array (in this case currentArr) at the end because all your appends point to the same array. A 2d list is just a list of pointers to other lists.

Now that you understand this, it is easier to understand why you get [[],[],[],[],[],[]] as your final output. Because you add to and then pop from currentArr over here currentArr.append(optionArr[num]) and over here currentArr.pop() to return it back to normal, your final version of currentArr will be what you passed in, i.e. []. Since result is a 2d array of 6 currentArrs, you will get [[],[],[],[],[],[]] as your returned value.

This may help you better how it all works, since it has diagrams as well: https://robertheaton.com/2014/02/09/pythons-pass-by-object-reference-as-explained-by-philip-k-dick/