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.

In your 2nd function's log, where are you getting the outputArray from? Does your 2nd function return something? — Shamas S
– Shamas S, Commented Oct 15, 2018 at 3:02
Oops made a slip. The two are equivalent and both return nothing. — stevenpcurtis
– stevenpcurtis, Commented Oct 15, 2018 at 3:04
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. — Ricky Mo
– Ricky Mo, Commented Oct 15, 2018 at 3:19
Is it possible to make this algorithm with the signature func permutations (_ n: Int, _ a: Array<Character>) -> [String] — stevenpcurtis
– stevenpcurtis, Commented Oct 15, 2018 at 3:25
Possibly helpful: Sequence-based enumeration of permutations with Heap's algorithm — Martin R
– Martin R, Commented Oct 15, 2018 at 3:47

Ricky Mo · Accepted Answer · 2018-10-15 03:26:26Z

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

answered Oct 15, 2018 at 3:26

Ricky Mo

7,7682 gold badges22 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Shamas S · Accepted Answer · 2018-10-15 03:33:13Z

0

Try something like this

func permutations (_ n: Int, _ a: Array<Character>) -> Array<Character> {
    var ary = a
    if (n == 1){
        print(String(ary));
        return ary
    }
    var array = Array<Character>()
    for i in 0..<n-1 {
        array = i == 0 ? permutations(n-1, ary) : permutations(n-1, array)
        array.swapAt(n-1, (n%2 == 1) ? 0 : i)
    }
    return permutations(n-1, array)
}

answered Oct 15, 2018 at 3:33

Shamas S

7,53910 gold badges49 silver badges59 bronze badges

Collectives™ on Stack Overflow

Heaps algorithm in swift

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related