2

我试图编写代码来确定排列。在 Wikipedia 中有一个简单算法的伪代码（来自 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
}
4

1 回答 1

0

这不是我真正喜欢的东西，但在我看来，问题在于 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)

结果对我来说是正确的，但看看你的想法。

于 2021-04-09T21:39:00.270 回答