Can anyone help me check this python code? [closed]

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. Closed 11 years ago.

I met a problem when I want to write a simple permutation code,

def permutation(Ori, Curr, used):
  if len(Ori) == len(Curr):
      #print Curr
      return

  for i in xrange(len(Ori)):
      if used[i]:
          continue
      used[i] = True
      Curr.append(Ori[i])
      print Curr,i," after append"
      permutation(Ori, Curr, used)    # further level
      used[i] = False
      print Curr,i," before delete"
      Curr = Curr[0:-1]               # Curr.pop() works
      print Curr,i," after delete"
  return

if __name__ == "__main__":
  used = [False]*3
  Curr = []
  permutation([1,2,3], Curr, used)

while result is not correct:

[1] 0  after append
[1, 2] 1  after append
[1, 2, 3] 2  after append
[1, 2, 3] 2  before delete
[1, 2] 2  after delete     <------
[1, 2, 3] 1  before delete <------
[1, 2] 1  after delete
[1, 2, 3] 2  after append
[1, 2, 3] 2  before delete
[1, 2] 2  after delete
[1, 2, 3] 0  before delete
[1, 2] 0  after delete
[1, 2, 2] 1  after append
[1, 2, 2] 1  before delete
[1, 2] 1  after delete
[1, 2, 3] 2  after append
[1, 2, 3] 2  before delete
[1, 2] 2  after delete

I don't know why the array has an extra number in the step I pointed out.

---

Sorry maybe I haven't made my quest开发者_如何转开发ion clear, I just want to know the reason why that recursion returned a list which I supposed it been shrinked. I wrote another piece of code, could anyone tell me the difference between the two commented sentence?(A = A[0:-1] and A.pop())

def f(A):
     if(len(A) == 10):
         return
     A.append('a')
     f(A)
     print A
 #   A = A[0:-1]                             
 #   A.pop()
     return

 if __name__ == "__main__":
    f([])

---

At the line

permutation(Ori, Curr, used)    # further level

you're passing pointers to the lists, not a copy of the lists. Doing this, when permutation modifies Curr, you see the modifications in the calling context. One possible solution is to call

permutation(Ori, Curr[:], used)    # further level

which passes a copy of Curr.

Why does Curr.pop() work?

Because it modifies Curr. It really removes the element from Curr before the function returns.

Using Curr = Curr[0:-1] creates a copy of Curr without one element. The element is not removed from the original list (to which the calling context still has access). So it doesn't do practically anything because the new list without the last element is forgotten as soon as the function returns.

Another possible solution would be not to change the received Curr at all - replace

Curr.append(Ori[i])

with

Curr = Curr + [Ori[i]]

---

There is already a function to generate permutations:

http://docs.python.org/library/itertools.html#itertools.permutations

The example code (defined in terms of product) is the "usual" generator-based implementation in my humble opinion.

In case it is useful to think about, here is code to generate all permutations of an iterable:

def permutations(iter):
    """
        >>> print(list( permutations(range(3)) ))
        [[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]
    """
    elements = list(iter)

    # base case
    if len(elements)==0:
        yield []

    for i,elem in enumerate(elements):
        withoutElem = elements[:i]+elements[i+1:]
        for perm in permutations(withoutElem):
            yield [elem]+perm