Home Generating permutations of a string in Swift
Post
Cancel

Generating permutations of a string in Swift

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. In Swift, we’ll create a generator NextPermutationGenerator using Sequence and IteratorProtocol to achieve the same - the generator will return the next permutation, and once the collection becomes reverse sorted, it will return nil, and the for..in loop will terminate.

Here’s how the algorithm works:

  1. 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.
  2. The element where this sorted order breaks, swap it with an element from the previous sequence which is its immediate upper bound.
  3. 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
59
60
61
62
struct NextPermutationGenerator<T: Comparable>: Sequence, IteratorProtocol {
    var inputArray: [T]
    
    mutating func next() -> [T]? {
        guard inputArray.count > 1 else { return nil }
        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 nil
        }
        // 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 inputArray
    }
}

// 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
8
func printPermutations(str: String) {
    let sortedStrArray = str.sorted()
    let sortedString = String(sortedStrArray)
    print(sortedString)
    for permutation in NextPermutationGenerator(inputArray: sortedStrArray) {
        print(String(permutation))
    }
}

Performance

After testing over multiple runs and test cases, I have found mixed results - the algorithm runs 2-3x better on some cases, and on some cases, its actually 2-3x slower.

Here are the average stats for Swift (lower is better):

1
2
paul: 0.009295940399169922 seconds
maheep: 0.003327012062072754 seconds

Here are the average stats for C++ (lower is better):

1
2
paul: 7623 microseconds
maheep: 2901 microseconds

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 attaching a comparable item to the underlying elements of our input array and sorting based on that, but the code to do that is gonna be even longer than above and a bit messy as well, which is why I’ve not made the effort of writing it. Here’s an approach if you want to try:

For e.g. we can take the input array as: ["s", "w", "i", "f", "t", "l", "y"]

We can use this to construct the following:

  • An array of numbers: [1, 2, 3, 4, 5, 6, 7]
  • And a dictionary of positions: [1: "s", 2: "w", 3: "i", 4: "f", 5: "t", 6: "l", 7: "y"]

Generate permutations of the array of numbers using the above generator, and return the output as permutedArrayOfNumbers.map { inputDictionary[$0] } in the next() function.

Conclusion

The code is definitely longer to write than the recursive approach (and will be even longer if you were to fix the above issues in it), so if you are in an interview and time is of the essence, go for the recursive solution. There are some significant performance gains in some cases, but in others, especially Paul’s magic word wombat, there are some performance losses as well. That’s weird because this code works better for wombats. 😝

Overall, this was a fun mental exercise and a nice trip to my CS roots.

This post is licensed under CC BY 4.0 by the author.