在下面介绍的情况下,我很难理解 Python 的工作原理。
我正在递归地计算一个列表的所有排列,我想返回一个包含所有这些排列的列表列表。如果我只是将它们打印出来,代码就可以正常工作,但是如果我尝试扩展最终的 [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]
为什么?
最佳答案
Python 使用对象。变量引用对象。如果您将列表添加到结果列表,然后进行修改,结果中的列表将反射(reflect)这些更改。
因此,您至少应该制作一份浅副本。例如,您可以使用:
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递归扩展列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47115151/