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)

Output: 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)

输出：

Output: ABC BAC CBA BCA ABC BAC

请注意，我们在此输出中没有得到 CAB，并且还重复了 "BAC" 和 "ABC"。

我不太明白这两者有何不同，想创建一个没有 inout 参数的算法版本。

Answer 1

Array 是 struct 并按 Swift 中的值传递。如果不使用 inout，则必须 return 数组才能接收更改。在不更新数组的情况下，for 循环中的每个 permutations(n-1, ary) 在交换之前基本上什么都不做。

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

swift 中的堆算法

Heaps algorithm in swift

swift

heaps-algorithm