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