Перестановка - DFS и возврат - нужна помощь в понимании раскручивания и возврата - PullRequest
Новая
       37

Перестановка - DFS и возврат - нужна помощь в понимании раскручивания и возврата

0 голосов
/ 19 февраля 2019

Следующий код используется для реализации перестановки массива Ints.Я не могу обернуть голову относительно того, как здесь происходит откат, особенно после того, как я напечатал [1, 2, 3], как мне вернуться и напечатать [1, 3, 2] - как именно работает path.removeLast()? 

func permute(_ nums: [Int]) -> [[Int]] {
    var res = [[Int]]()
    var path = [Int]()
    var isVisited = [Bool](repeating: false, count: nums.count)
    var counter = 0
    dfs(&res, &path, &isVisited, nums)

    return res
}

private func dfs(_ res: inout [[Int]], _ path: inout [Int], _ isVisited: inout [Bool], _ nums: [Int]) {
    guard path.count != nums.count else {
        res.append(path)
        return
    }

    for (i, num) in nums.enumerated() where !isVisited[i] {
        path.append(num)
        isVisited[i] = true
        dfs(&res, &path, &isVisited, nums)
        isVisited[i] = false
        path.removeLast()
    }

1 Ответ

0 голосов
/ 20 февраля 2019

Иногда проще всего вернуться назад на примере.Возьмите массив [1,2,3], затем, используя ваш подход, вы сделаете что-то вроде этого: 

Before removing: 1
Before removing: 1 2
Before removing: 1 2 3
After removing: 1 2
After removing: 1
Before removing: 1 3
Before removing: 1 3 2
After removing: 1 3
After removing: 1
After removing:
Before removing: 2
Before removing: 2 1
Before removing: 2 1 3
After removing: 2 1
After removing: 2
Before removing: 2 3
Before removing: 2 3 1
After removing: 2 3
After removing: 2
After removing:
Before removing: 3
Before removing: 3 1
Before removing: 3 1 2
After removing: 3 1
After removing: 3
Before removing: 3 2
Before removing: 3 2 1
After removing: 3 2
After removing: 3
After removing:

Эффективно то, что вы делаете, генерирует все возможные подпоследовательности для каждой перестановки и затем удаляет их (отсюдаудалить последнее), пока не вернетесь к пустому списку.Если вы нарисовали дерево рекурсии для предоставленного вами кода, у вас будет 31 узел (по одному на каждую строку выше).Можем ли мы сделать лучше?Да.Рассмотрим следующее дерево для того же примера: enter image description here

(здесь более симпатичная версия аналогичного дерева с символами вместо целых чисел: Перестановка строки с использованием алгоритма обратного отслеживания )

Большое улучшение.Только 10 узлов в дереве, и последний уровень в дереве имеет все перестановки.Это может быть достигнуто с помощью обратного отслеживания и является гораздо более простым примером для понимания.Все, что вы делаете, это меняете узлы вместо генерации всех возможных подпоследовательностей для каждой перестановки.Свифт реализации этого второго, лучшего подхода можно найти здесь: https://leetcode.com/problems/permutations/discuss/229627/Swift

...