Heaps algorithm in swift

Question

I have an implementation of Heap's algorithm in Swift that I am trying to convert to NOT use inout parameters.

However I get different results for each (the second is wrong, delivering a repeated permutation). What is going wrong, and how do I fix it?

Original implementation:

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

Implementation without inout parameters:

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:

Output: ABC BAC CBA BCA ABC BAC

Note we don't get CAB in this output, and also have a repetition of "BAC" and "ABC".

I can't quite see how the two are not equivalent, and want to create a version of this algorithm without the inout parameter.

Answer 1

Array is struct and passed by value in Swift. If you don't use inout, you have to return the array in order to receive the change. Without updating the array, every permutations(n-1, ary) inside the for-loop basically does nothing before you swap.

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