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 [[], [], [], [], [], []].

If you are trying to find all permutations, are you sure that [[3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]] is a valid result? — PoorProgrammer
– PoorProgrammer, Commented Aug 6, 2019 at 15:49
Your right! I probably copied the wrong output after I made changes to my code. But, let's just ignore that. — Francis Pokemon
– Francis Pokemon, Commented Aug 6, 2019 at 16:03
John Coleman's answer will fix your code so you should accept it, but look at mine to understand why it was happening. — PoorProgrammer
– PoorProgrammer, Commented Aug 6, 2019 at 16:11

John Coleman · Accepted Answer · 2019-08-06 15:52:15Z

3

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

edited Aug 6, 2019 at 15:52

answered Aug 6, 2019 at 15:45

John Coleman

52.1k7 gold badges59 silver badges127 bronze badges

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

Comments

PoorProgrammer · Accepted Answer · 2019-08-06 16:09:31Z

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/

Collectives™ on Stack Overflow

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

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related