3

I'm having difficulty creating a 2D list of permutations. Here is a minimal code to reproduce the problem

class Solution:
def permute(self, A):
    A = sorted(A)
    print A
    A_out = []
    A_out.append(A)
    for iter0 in range(4):
        A[0] = A[0] + 1
        print A
        A_out.append(A)
    return A_out

sol = Solution()
A = [1, 2, 3]
print sol.permute(A)

For this particular input(1, 2, 3) the output is

[1, 2, 3]
[2, 2, 3]
[3, 2, 3]
[4, 2, 3]
[5, 2, 3]
[[5, 2, 3], [5, 2, 3], [5, 2, 3], [5, 2, 3], [5, 2, 3]]

but the desired output is

[1, 2, 3]
[2, 2, 3]
[3, 2, 3]
[4, 2, 3]
[5, 2, 3]
[[1, 2, 3], [2, 2, 3], [3, 2, 3], [4, 2, 3], [5, 2, 3]]

I think it has something to do deep copy/ shallow copy thing but I am not sure how to correct this as I am not very familiar with Python. How can I fix it?

SuperBiasedMan
  • 9,814
  • 10
  • 45
  • 73
Gaurav Mittal
  • 69
  • 8
  • 1
    Thanks for creating a minimal example. But in reference to your original permutation maker algorithm: there is a fast permutation generator in the standard [itertools](https://docs.python.org/2/library/itertools.html#itertools.permutations) module. However, unlike your code, `itertools.permutations()` will produce duplicate permutations if the input iterable contains repeated elements. It's easy enough to use a set to filter those out, but that becomes inefficient, especially if the input iterable has multiple repeated values. – PM 2Ring Aug 18 '15 at 12:19
  • FWIW, you may also be interested in [this permutation code](http://stackoverflow.com/a/31678111/4014959). – PM 2Ring Aug 18 '15 at 12:29
  • @PM2Ring: I know about itertools.permutations() but the question I was trying to solve specifically asked not to use itertools.permutations() – Gaurav Mittal Aug 18 '15 at 12:43

1 Answers1

5

It is indeed about shallow copies. The list A you keep appending always refers to the same value. This is related to the mutability of lists in Python.

You need to append a new copy of the list each time to make them independent of each other. You can do that using the slice operator [:] because it creates a new copy of the list. So you can just use it when calling append

def permute(self, A):
    A = sorted(A)
    print A
    A_out = []
    A_out.append(A[:])
    while (self.checkVal(A) != -1) :
        A = self.nextState(A,self.checkVal(A))
        print A
        A_out.append(A[:])
    return A_out
SuperBiasedMan
  • 9,814
  • 10
  • 45
  • 73
  • I was searching a lot regarding this for past few hours but couldn't get the answer. Thank you for this answer, it finally solved my problem. – Gaurav Mittal Aug 18 '15 at 12:15
  • @GauravMittal Glad to help! [This blogpost](http://www.jeffknupp.com/blog/2013/02/14/drastically-improve-your-python-understanding-pythons-execution-model/) is helpful for explaining mutability. It is a bit complicated but it's well worth a read when you have time because it explains a lot of how Python behaves under the hood. – SuperBiasedMan Aug 18 '15 at 13:49