swift - 快速堆算法

Question

我在 Swift 中有一个堆算法的实现，我试图将其转换为不使用 inout 参数。

但是我得到了不同的结果（第二个是错误的，提供了重复的排列）。出了什么问题，我该如何解决？

原始实现：

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

没有 inout 参数的实现：

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

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)
}

Answer 2

尝试这样的事情

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)
}