Swift 中的值与引用类型，使用堆排列算法的维基百科实现作为示例

Question

我正在尝试编写用于确定排列的代码。在维基百科中有一个简单算法的伪代码（来自 BR Heap）。我试图翻译伪代码

procedure generate(k : integer, A : array of any):
    if k = 1 then
        output(A)
    else
        // Generate permutations with kth unaltered
        // Initially k == length(A)
        generate(k - 1, A)

        // Generate permutations for kth swapped with each k-1 initial
        for i := 0; i < k-1; i += 1 do
            // Swap choice dependent on parity of k (even or odd)
            if k is even then
                swap(A[i], A[k-1]) // zero-indexed, the kth is at k-1
            else
                swap(A[0], A[k-1])
            end if
            generate(k - 1, A)

        end for
    end if

我的代码给出了正确的排列数，但我可以看到有一些缺失，还有一些加倍。

原来这是基于我对 Swift 值类型与引用类型的误解。

这是我的（无法正常工作）代码：

func perms(k: Int, arr: [Any]) {   //NOTE that this is NOT providing the correct permuations at this time.  Some are doubled, some are missing (Yet the total permuations in number are correct)
    var variedArray = arr
    if k == 1 {
        counter += 1  //this is not part of the Wikipedia psuedo code, I just wanted to count that I was at least getting the right number of permutations
        outputArray.append(variedArray)  //this is appending to an array that contains all the permutation after all is done
        
    } else {
        
        perms(k: k - 1 , arr: variedArray)
        for i in 0..<k-1 {
            if (k)%2 == 0 {  // if even do this
                variedArray.swapAt(i, k-1)
            } else {
                variedArray.swapAt(0, k-1)
            }
            perms(k: k - 1, arr: variedArray)
        }
    }
    
    return
}

Answer 1

这真的不是我喜欢的东西，但在我看来问题好像是 Swift 数组是按值传递的，所以我们需要一个 inout 参数.所以我这样翻译：

func generate<T>(k:Int, a: inout Array<T>) {
    if k == 1 {
        print(a)
        return
    }
    generate(k:k-1, a:&a)
    for i in 0..<k-1 {
        if k%2 == 0 {
            a.swapAt(i, k-1)
        } else {
            a.swapAt(0, k-1)
        }
        generate(k:k-1, a:&a)
    }
}

这是我的测试：

    var arr = [1,2,3]
    generate(k:arr.count, a:&arr)

我觉得结果不错，但看看你怎么想。

Swift 中的值与引用类型，使用堆排列算法的维基百科实现作为示例

Value vs Reference Types in Swift using Wikipedia implementation of Heap's permutation algorithm as example

swift

algorithm

permutation

heaps-algorithm