Список 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.Если так, как я могу это исправить?

Большое спасибо.

Ян

Answer 1

Вы правы, когда вы добавляете, вы помещаете список в self.queues, это через адрес.Но это не проблема, проблема в том, что вы позже продолжаете модифицировать этот же объект, и поэтому его очистка также означает, что self.queues содержит указатель на пустой список.

Вам необходимо сделать копиюпуть (например, self.queues.append(path[:]) и добавьте его в очередь.Или в общем случае вы можете использовать модуль Python для копирования (либо мелкое, либо глубокое копирование в зависимости от вашего варианта использования https://docs.python.org/2/library/copy.html)

Answer 2

Ваша проблема не в self.queues, а в том, как вы справляетесь path.Когда вы передаете path его в функцию, вы передаете его по присваиванию , а не по его значению.

Поэтому, когда вы добавляете 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)