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. Let’s try it in Swift.

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

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:

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.

/*
 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.