This post is a presentation of my attempt to create an iterative way to generate permutations of a string in Swift, similar to C++ STL’s `next_permutation`

function. I got the idea to solve this problem while reading one of the challenges (Challenge 14) in Paul Hudson’s Swift Coding Challenges book.

## The Algorithm

In C++, `next_permutation`

can be called in a loop and will keep generating permutations of a collection and return true till the collection becomes completely reverse sorted, after which it returns false. Let’s try it in Swift.

Here’s how the algorithm works:

- Given a sequence, start iterating over it from last. Keep iterating as long as the elements appear in non-decreasing order. If we reach the last element, we cannot generate anymore permutations and we’ll return.
- The element where this sorted order breaks, swap it with an element from the previous sequence which is its immediate upper bound.
- Reverse the sequence from breaking element onwards.

I’ve listed my implementation below. Since swift arrays don’t have a built-in binary search, an extension has also been provided for that (code copied and adapted from Vadim Yelagin’s answer on StackOverflow):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

func getNextPermutation<T: Comparable>(inputArray: inout [T]) -> Bool {
guard inputArray.count > 1 else { return false }
var sortedOrderSequenceLength = 1
// start from last and see how much its sorted in increasing order
for i in (0...inputArray.count-2).reversed() {
if inputArray[i+1] <= inputArray[i] {
sortedOrderSequenceLength += 1
} else {
break
}
}
if sortedOrderSequenceLength == inputArray.count {
// We are at the last permutation already, return
return false
}
// the element where this sorted order breaks, swap it with the element from the sequence which is just more than it, i.e. the upper bound
let breakingElementIndex = inputArray.count - sortedOrderSequenceLength - 1
let indexOfUpperBound = inputArray.binarySearch(start: breakingElementIndex + 1, end: inputArray.count - 1, reversed: true) { $0 < inputArray[breakingElementIndex] }
inputArray.swapAt(breakingElementIndex, indexOfUpperBound)
// reverse the sequence that is present after breakingElementIndex
var end = inputArray.count - 1
var start = breakingElementIndex + 1
while start < end {
inputArray.swapAt(start, end)
end -= 1
start += 1
}
return true
}
// Found and adapted from here: https://stackoverflow.com/a/33674192/4385319
extension RandomAccessCollection where Element: Comparable {
func binarySearch(start: Index, end: Index, reversed: Bool = false, predicate: (Element) -> Bool) -> Index {
var (low, high) = (start, end)
if !reversed {
while low != high {
let mid = index(low, offsetBy: distance(from: low, to: high)/2)
if predicate(self[mid]) {
low = index(after: mid)
} else {
high = mid
}
}
return low
} else {
while low != high {
// RandomAccessCollection inherits from BidirectionalCollection, so this is fine
let mid = index(high, offsetBy: distance(from: high, to: low)/2)
if predicate(self[mid]) {
high = index(before: mid)
} else {
low = mid
}
}
return high
}
}
}

Here’s how we can use our generator:

1
2
3
4
5
6
7

func printPermutations(str: String) {
var arr = Array(str.sorted())
print(String(arr))
while getNextPermutation(inputArray: &arr) {
print(String(arr))
}
}

## Performance

After testing over multiple runs and test cases, I have found mixed results - the algorithm runs faster on some cases, particularly where input is large, and on some cases, like small inputs, its slower. For example, on Paul’s magic test word **wombat**, the code is slower. Strangely, its faster for the input **wombats**.

## Issues so far

The good thing about the recursive solution is that unlike the iterative solution presented above, it has no limitation about requiring the underlying elements to conform to `Comparable`

protocol. We can overcome this limitation in the iterative solution as well, by providing our own sorting function based on position of an element as a parameter to the `getNextPermutation()`

function.

## And the winner is…

*Dr. Niklaus Wirth, who wrote the following algorithm to generate all permutations of a given array, that blows both mine and Paul’s solutions out of the water for every test case, and is simple enough, with none of the issues identified above.*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/*
Code taken from the following link: https://github.com/raywenderlich/swift-algorithm-club/blob/master/Combinatorics/Combinatorics.playground/Contents.swift
Prints out all the permutations of the given array.
Original algorithm by Niklaus Wirth.
See also Dr.Dobb's Magazine June 1993, Algorithm Alley
*/
func permuteWirth(_ a: [Character], _ n: Int) {
if n == 0 {
print(String(a)) // display the current permutation
} else {
var a = a
permuteWirth(a, n - 1)
for i in 0..<n {
a.swapAt(i, n)
permuteWirth(a, n - 1)
a.swapAt(i, n)
}
}
}

Still taking me to that data structures and algorithms class.