リストを再帰的に拡張する

Question

以下に示す状況でPythonがどのように動作するかを理解するのが難しいです。

私はリストのすべての並べ替えを再帰的に計算しています。これらの並べ替えを含むリストのリストを返したいと思います。最終的な[結果]を拡張しようとすると、入力リストと同じ値のリストが表示されます（単語リストを繰り返してごめんなさい）。

これは

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)がゼロであるかどうかをチェックします。したがって、isinstance(..)を使用する必要があります。

より効率的な方法は、リストを一度構築して、それをシステム収集結果に渡すことです。例：

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