python - 在进行递归时，Python 列表未按预期传递

Question

我正在尝试按以下方式解决N 队列 ：

class Solution(object):
    def __init__(self):
        self.queues = []

    def DFS(self, n, row, col, pie, na, path):
        if row == n:
            print 'current recursion path: ', path
            self.queues.append(path)
            print 'paths within the recursion: ', self.queues
            return 

        for c in range(n):
            if (c not in col) and (c + row not in pie) and (row-c not in na):
                col.add(c)
                pie.add(c+row)
                na.add(row-c)
                # self.queues.append(c)
                # path += str(c)
                path.append(c)
                # print 'row: ', row, 'col: ', c, path
                self.DFS(n, row + 1, col, pie, na, path)
                col.remove(c)
                pie.remove(c+row)
                na.remove(row-c)
                # path = path[:-1]
                path.pop()
            # else:
                # path.pop()
        return None
        # print '\n'

    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        col = set()
        pie = set()
        na = set()
        print 'before recursion: ', self.queues
        self.DFS(n, 0, col, pie, na, [])
        print 'after recursion: ', self.queues
        # return self.reslutPrint(n)

我得到以下打印输出：

before recursion:  []
current recursion path:  [1, 3, 0, 2]
paths within the recursion:  [[1, 3, 0, 2]]
current recursion path:  [2, 0, 3, 1]
paths within the recursion:  [[2, 0, 3, 1], [2, 0, 3, 1]]
after recursion:  [[], []]

如您所见，递归为每条路径得到了正确的答案，但是，答案没有self.queues正确地附加到全局变量中。你能告诉我为什么会这样吗？

我猜这是因为当我将列表附加到 时self.queues，它给出了地址而不是实际值self.queues。如果是这样，我该如何解决这个问题？

非常感谢。

伊恩

标签： pythonlistrecursion

Answer 1

您遇到的问题不self.queues在于您的处理方式，而在于您的处理方式path。当你将path它传递给一个函数时，你是通过 assignment 传递它，而不是它的值。

因此，当您添加path到self.queues并稍后执行path.pop()时，它会影响任何path被引用的地方，包括在self.queues.

这是问题的一个简单示例：

>>> a = []
>>> b = [1, 2, 3]
>>> a.append(b)
>>> b.pop()
>>> print(a)
[[1, 2]]

那么，纠正这个问题的最佳方法是什么？正如其他人所建议的那样，您可以在添加列表之前复制self.queues.append(path[:])您的列表，使用. 但我认为仔细检查会得出另一个答案：将新的递归传递给 path每个新级别。而不是path.append(c)，尝试self.DFS(n, row + 1, pie, na, path + [c]。通过这种方式，您采用了一种更实用的不变性方法（您可以更进一步，通过使用不可变数据结构来强制实现不变性，例如tuple）。以下是您的代码使用这种方法的外观：

def DFS(self, n, row, col, pie, na, path):
    if row == n:
        print 'current recursion path: ', path
        self.queues.append(path)
        print 'paths within the recursion: ', self.queues
        return 

    for c in range(n):
        if (c not in col) and (c + row not in pie) and (row-c not in na):
            col.add(c)
            pie.add(c+row)
            na.add(row-c)
            self.DFS(n, row + 1, col, pie, na, path + [c])
            col.remove(c)
            pie.remove(c+row)
            na.remove(row-c)