Понимание перестановок с возвратом - PullRequest
Новая
       24

Понимание перестановок с возвратом

2 голосов
/ 11 февраля 2020

Я пытаюсь выяснить, как работает следующее решение обратного отслеживания для генерации всех перестановок целых чисел, представленных в виде списка: 

def permutations(arr):
    res = []
    backtrack(arr, [], set(), res)
    print(res)

def backtrack(arr, temp, visited, res):
    if len(temp) == len(arr):
        res.append(temp[:])
    else:
        for num in arr:
            if num in visited: continue
            visited.add(num)
            temp.append(num)
            backtrack(arr, temp, visited, res)
            visited.remove(num)
            temp.pop()

Выполнение со следующим: 

permutations([1, 2, 3])

Результат, как и ожидалось:

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [ 3, 1, 2], [3, 2, 1]]

Что я не понимаю, так это вызов temp.pop() в конце l oop. Я знаю, что pop() отбрасывает последний элемент списка, но зачем это здесь нужно?

Буду очень признателен, если кто-нибудь сможет мне это объяснить.

1 Ответ

1 голос
/ 11 февраля 2020

Это необходимо, потому что на следующей итерации функция снова будет append элементом, поэтому, если вы не сделали pop заранее, список будет увеличиваться в размере. Поскольку backtrack добавляет результаты только в том случае, если длина temp равна длине исходного arr, ничего не будет добавлено после первой перестановки [1, 2, 3] (поскольку с этого момента список temp продолжает расти) .

Мы можем просто удалить эту строку (temp.pop()) и посмотреть, как будут выглядеть результаты: 

[[1, 2, 3]]

Теперь, если мы также изменим, результаты добавляются всякий раз, когда len(temp) >= len(arr), тогда мы Вы увидите, как temp увеличивается в размере: 

[[1, 2, 3], [1, 2, 3, 3], [1, 2, 3, 3, 2], [1, 2, 3, 3, 2, 3]]

Здесь мы получаем меньше результатов, потому что для каждого рекурсивного вызова за пределами [1, 2, 3] список temp немедленно копируется, даже не достигая for l. oop.

...