swiftalgorithmpermutationheaps-algorithm

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


I was trying to write code for determining permutations. In Wikipedia there is psuedo code for a simple algorithm (from BR Heap). I attempted to translate the psuedo code

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

My code gives the correct number of permutations yet I can see that there are some missing and others doubled up.

This turned out to be based on my misunderstanding of Swift value types versus reference types.

Here is my (not working propertly) code:

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
}

Solution

  • This is not really my kind of thing, but it looks to me at a glance as if the problem is that Swift arrays are passed by value, so we need an inout param here. Therefore I translated it like this:

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

    And here's my test:

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

    The result looks right to me but see what you think.