리스트를 재귀 적으로 확장하는 파이썬

Question

아래에 제시된 상황에서 파이썬이 어떻게 작동하는지 이해하는데 어려움이 있습니다.

나는 목록의 모든 순열을 재귀 적으로 계산하고 있으며 모든 순열을 가진 목록의 목록을 반환하고자합니다. 코드를 그냥 인쇄하면 잘 작동하지만 최종 결과를 확장하려고하면 입력 목록과 동일한 값의 목록으로 끝납니다 (단어 목록을 반복하는 데 죄송합니다)

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) 

그리고 결과 : 내 코드입니다

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

내가 말했듯이, 난 그냥이 예상대로 작동 결과를 인쇄하는 경우 :

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) 

출력 :

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

이유는 무엇입니까?

Answer 1

Python은 개체와 함께 작동합니다. 변수는 객체를 참조합니다. 결과 목록에 목록을 추가 한 다음 수정하면 결과의 목록에 변경 내용이 반영됩니다.

따라서 최소한 을 얕은 복사본으로 만들어야합니다. 예를 들면 다음과 같습니다.

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)

그럼에도 불구하고이 코드 조각은 여전히 ​​비효율적이며 이해하기 어렵습니다. not(len(l))은 개체에 len(..)이 있는지 확인하지 않습니다. len(l)이 0인지 확인합니다. 따라서 isinstance(..)을 사용해야합니다.

보다 효율적인 방법은 res 목록을 한 번 작성하여 시스템 수집 결과를 전달하는 것입니다. 예 :

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), [])