Python extending list recursively

Question

I'm having some difficulty in understanding how Python works in the situation presented below.

I'm computing all permutations of a list recursively, and I want to return a list of lists with all those permutations. Code works fine if i just print them out, but if i try to extend the final [result] i end up with a list of lists with the same value as my input list (sorry for repeating the word list)

This is my code:

def swap(l, i, j):
  l[i], l[j] = l[j], l[i]

def compute(l):
  if not len(l):
    print 'no list'
  start, end = 0, len(l) - 1
  return _compute(l, start, end)

def _compute(l, start, end):
  res = []
  if start == end:
    return [l]
  else:
    for i in range(start, end+1):
      swap(l, start, i)
      res.extend(_compute(l, start+1, end))
      swap(l, start, i) # backtrack
  return res

l = [1,2,3]
print compute(l)

And the result:

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

Like i said, if i just print out the results it works as expected:

def swap(l, i, j):
  l[i], l[j] = l[j], l[i]

def compute(l):
  if not len(l):
    print 'no list'
  start, end = 0, len(l) - 1
  _compute(l, start, end)


def _compute(l, start, end):
  if start == end:
    print l
  else:
    for i in range(start, end+1):
      swap(l, start, i)
      _compute(l, start+1, end)
      swap(l, start, i) # backtrack

l = [1,2,3]

compute(l)

The output:

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

Why?

Answer 1

Python works with objects. Variables refer to objects. If you add the list to the resulting list, and then make modifications, the list in your result will thus reflect those changes.

You thus should make at least a shallow copy. You can this for instance with:

def _compute(l, start, end):
  res = []
  if start == end:
    return [l[:]]  # make a shallow copy
  else:
    for i in range(start, end+1):
      swap(l, start, i)
      res.extend(_compute(l, start+1, end))
      swap(l, start, i) # backtrack
  return res

l = [1,2,3]
print compute(l)

Nevertheless, this code fragment is still quite inefficient, and hard to understand. Note that not(len(l)) does not check if the object has a len(..): it checks if len(l) is zero. You thus should use isinstance(..).

A more efficient approach would be to construct the res list once, and pass it through the system collection results. For example:

def _compute(l):
  def _calc(start, end, res):
    if start < end-1:
        for i in range(start,end):
          swap(l,start,i)
          _calc(start+1, end, res)
          swap(l,start,i)
    else:
      res.append(l[:])
    return res
  return _calc(0, len(l), [])