4

I have implemented a pretty basic algorithm to print permutations of a list in python. However, I am unable to figure out the reason for the behavior of a property of an object. Here's the code :

class Solution:
    def permute(self, A):
        self.ans = []
        self.generate_perm(list(A))       
        return self.ans

    def generate_perm(self, A, k=0):
        #print A, k
        #print self.ans
        if k == len(A):
            self.process(A)
        else:
            for i in xrange(k, len(A)):
                A[k], A[i] = A[i], A[k]
                self.generate_perm(A, k+1)
                A[k], A[i] = A[i], A[k]

    def process(self,A):
        print A
        self.ans.append(A)


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

The output of the above snippet is : 

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
[[1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3], [1, 2, 3]]

I was expecting the append method to add the input to process(), but somehow it just duplicates the last appended item to the number of terms existing in list + adds one more.

I think it should be fairly direct.

Ashwini Khare
  • 1,645
  • 6
  • 20
  • 37
  • 4
    Because they're all references to *the same list object*... – jonrsharpe Jun 03 '15 at 18:06
  • 3
    `self.ans.append(A[:])` -- appends a copy of the current mutation. – Steven Rumbalski Jun 03 '15 at 18:07
  • 2
    just use itertools.permutations https://docs.python.org/3.5/library/itertools.html#itertools.permutations – hellow Jun 03 '15 at 18:07
  • 2
    @cookiesoft But what if you want to do it yourself, as a neat little beginner project? – Zizouz212 Jun 03 '15 at 18:07
  • jonrsharpe , @StevenRumbalski : Thanks. Btw, A[:] - is essentially the entire list, and when I call process(), A is a mutation. Why is making a copy necessary, since you are just appending anyways and how does entire self.ans get effected? – Ashwini Khare Jun 03 '15 at 18:13
  • 1
    See e.g. http://stackoverflow.com/q/2612802/3001761, or read http://nedbatchelder.com/text/names.html. – jonrsharpe Jun 03 '15 at 18:16
  • Wow, Thanks for the reference. Learned a new thing! – Ashwini Khare Jun 03 '15 at 18:18
  • 2
    @AshwiniKhare: You said it: "`A` is a mutation." Every time you mutate `A` that mutation is accessible by all references to it. You should take the time to read [Facts and myths about Python names and values](http://nedbatchelder.com/text/names.html). There are more places in Python that this comes up. – Steven Rumbalski Jun 03 '15 at 18:19

0 Answers0