Python 递归扩展列表

Question

我很难理解 Python 在下面介绍的情况下是如何工作的。

我正在递归地计算一个列表的所有排列，我想 return 一个包含所有这些排列的列表列表。如果我只是将它们打印出来，代码就可以正常工作，但是如果我尝试扩展最终的 [result]，我最终会得到一个与我的输入列表具有相同值的列表列表（抱歉重复单词列表）

这是我的代码：

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<b>[:]</b>]  # 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(..).

一种更有效的方法是构造一次 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), [])

Python 递归扩展列表

Python extending list recursively

python

algorithm

backtracking