스택 및/또는 큐를 사용하여 파이썬에서 int리스트 순열

Question

정수리스트 ([1,2,3])를 취하는 모든 메소드 def permutations(lst)을 쓰려고합니다. 가능한 모든 순열을 인쇄합니다 , 없이 재귀를 사용하여. 이 방법에서는 스택 및/또는 큐를 사용해야합니다.

지금까지 내가 가진 :

class Queue: 

    def __init__(self): 
     self.items = [] 

    def isEmpty(self): 
     return self.items == [] 

    def enqueue(self, item): 
     self.items.insert(0,item) 

    def dequeue(self): 
     return self.items.pop() 

    def size(self): 
     return len(self.items) 

    def __rep__(self): 
     return str(self.items) 


def permutation(lst): 
    temp = [0] * len(lst) 
    q = Queue() 
    q.enqueue(lst) 
    i = 1 
    while i < len(lst): 
     if temp[i] < i: 
      j = temp[i] if i % 2 else 0 
      lst[j], lst[i] = lst[i], lst[j] 
      q.enqueue(lst) 
      temp[i] += 1 
      i = 1 
     else: 
      temp[i] = 0 
      i += 1 

    return q.__rep__() 


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

하지만 얻을 출력은 : [[3, 2, 1, 3, 2, 1, 3, 2, 1, 3 , 2, 1], [3,2,1], [3,2,1].

그러나 enqueueing 대신 lst를 인쇄 할 때 (단지 인쇄로 enqueue 행을 대체 할 때) 정확한 결과를 얻습니다. [1,2,3], [2, 1, 3], [3,1,2], [1, 3,2], [2, 3,1], [3,2,1] .

대기열을 사용하도록 코드를 수정하려면 어떻게해야합니까? 어떤 제안도 감사합니다.

Answer 1

문제

문제는 enqueue에 목록 참조입니다 : 당신은 같은 목록에 여섯 참조를 얻었다. 하나의 요소를 변경할 때마다 모든 요소가 변경됩니다. 중간 지점에서 q 인쇄, 당신은 효과를 볼 수 있습니다 :

이

else: 
     temp[i] = 0 
     i += 1 
    print ("temp", temp) 
    print ("lst", lst) 
    print("q", q.__rep__()) 

출력 : 당신이 대기열 때 대신

temp [0, 1, 0] 
lst [2, 1, 3] 
q [[2, 1, 3], [2, 1, 3]] 
temp [0, 0, 0] 
lst [2, 1, 3] 
q [[2, 1, 3], [2, 1, 3]] 
... 
temp [0, 0, 2] 
lst [3, 2, 1] 
q [[3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]] 
temp [0, 0, 0] 
lst [3, 2, 1] 
q [[3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]] 
[[3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1], [3, 2, 1]] 

목록의 사본합니다

def enqueue(self, item): 
    self.items.insert(0, item[:]) 

을

그러면 원하는 결과가 나옵니다.