Алгоритм куч в быстром

Question

У меня есть реализация алгоритма Heap в Swift, которую я пытаюсь преобразовать, чтобы НЕ использовать входные параметры.

Однако я получаю разные результаты для каждого (второе неверно, предоставляя повторную перестановку).Что не так, и как я могу это исправить?

Исходная реализация:

func permutations(_ n:Int, _ a: inout Array<Character>) {
    if n == 1 {print(String(a)); return}
    for i in 0..<n-1 {
        permutations(n-1,&a)
        a.swapAt(n-1, (n%2 == 1) ? 0 : i)
    }
    permutations(n-1,&a)
}
var arr = Array("ABC".characters)
permutations(arr.count,&arr)

Вывод: ABC BAC CAB ACB BCA CBA

Реализация без входных параметров:

func permutations (_ n: Int, _ a: Array<Character>) {
    var ary = a
    if (n == 1){
        print(String(ary));
        return
    }
    for i in 0..<n-1 {
        permutations(n-1, ary)
        ary.swapAt(n-1, (n%2 == 1) ? 0 : i)
    }
    permutations(n-1, ary)
}
var arr = Array("ABC".characters)
permutations(arr.count,arr)

вывод:

Выход: ABC BAC CBA BCA ABC BAC

Обратите внимание, что мы не получаем CAB вэтот вывод, а также есть повторение «BAC» и «ABC».

Я не совсем понимаю, как они не эквивалентны, и хочу создать версию этого алгоритма без параметра inout.

Answer 1

Попробуйте что-то вроде этого

func permutations (_ n: Int, _ a: Array<Character>) -> Array<Character> {
    var ary = a
    if (n == 1){
        print(String(ary));
        return ary
    }
    var array = Array<Character>()
    for i in 0..<n-1 {
        array = i == 0 ? permutations(n-1, ary) : permutations(n-1, array)
        array.swapAt(n-1, (n%2 == 1) ? 0 : i)
    }
    return permutations(n-1, array)
}

Answer 2

Array равно struct и передается по значению в Swift.Если вы не используете inout, вы должны вернуть массив, чтобы получить изменения.Без обновления массива каждый permutations(n-1, ary) внутри цикла for практически ничего не делает перед тем, как вы меняете его.

func permutations (_ n: Int, _ a: Array<Character>) -> Array<Character> {
    var ary = a
    if (n == 1){
        print(String(ary));
        return ary
    }
    for i in 0..<n-1 {
        ary = permutations(n-1, ary)
        ary.swapAt(n-1, (n%2 == 1) ? 0 : i)
    }
    return permutations(n-1, ary)
}