Find all permutations of a string in Swift

StringPermutations.swift

//: Playground - noun: a place where people can play

import Foundation

func stringPermutations(s: String) -> [String] {
 return ["?"]
}

/*
 Avoid using C++'s std::next_permutation or similar features in other languages to solve this challenge. Implement the algorithm yourself, since this is what you would be asked to do during a real interview.
 
 Given a string s, find all its potential permutations. The output should be sorted in lexicographical order.
 
 Example
 
 For s = "CBA", the output should be
 stringPermutations(s) = ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"];
 For s = "ABA", the output should be
 stringPermutations(s) = ["AAB", "ABA", "BAA"].
 Input/Output
 
 [time limit] 20000ms (swift)
 [input] string s
 
 A string containing only capital letters.
 
 Guaranteed constraints:
 1 ≤ s.length ≤ 5.
 
 [output] array.string
 
 All permutations of s, sorted in lexicographical order.
 */

var string = "A"

/*
 Examples:
 "A" -> ["A"] 1
 "AB" -> ["AB", "BA"] 2
 "ABC" -> ["CAB", "ACB", "ABC", "CBA", "BCA", "BAC"] 6
 
 "L" -> ["L"]
   - take that set of permutations ["L"] and
   - distrbute the next letter "I" across each one
 "I" -> ["IL", "LI"]
   - take this new set of permutations ["IL", "LI"] and
   - distribute the next letter "N" across each one
 "N" -> ["NIL", "INL", "ILN", "NLI", "LNI", "LIN"]
 
   - distribute "K"
 "LINK" -> ["KNIL", "NKIL", "NIKL", "NILK",
            "KINL", "IKNL", "INKL", "INLK", 4 more times....
 
 What do we do w/ dupe letters? Do we remove them?
 
 */

func permutations(source: String) -> [String] {
    guard source.count > 0 else {
        print("source must not be empty.")
        return []
    }
    // Start recursing at the second index of the string
    // Priming the recursion with the first character
    let firstCharacter = String(describing: source.first!)
    return permutationHelper(source: source, currentPosition:1, perms: [firstCharacter])
}

// Recursive function that takes the current index of the source string
// creates character permutations with it, and adds them to a list of permutations
func permutationHelper(source:String, currentPosition:Int, perms:[String]) -> [String] {
    
    // Be sure to exit when we hit the end of the list.
    let currentIndex = String.Index(encodedOffset: currentPosition)
    if currentIndex == source.endIndex {
        return perms
    }
    
    let currentCharacter = source[currentIndex]
    var newPerms = [String]()
    
    // Create new permutations for each string in current set of permutations
    for perm in perms {
        let distributions = distribute(newChar:currentCharacter, target: perm)
        newPerms.append(contentsOf: distributions)
    }
    
    let newPosition = currentPosition + 1
    return permutationHelper(source: source, currentPosition: newPosition, perms: newPerms.sorted())
}

// Takes a new character string and a target string as input.
// The new character is placed at each position of the target string
// between each letter. Each time it is placed a copy of that new string is
// added to an array.

// Note because of Swift's new string encoding capabilities we need to be
// careful with any encoding other than UTF-8 (probably) because our
// usage of String.Index assumes we're working with UTF-8.

func distribute(newChar:Character, target:String) -> [String] {
    var distribution = [String]()

    for i in 0..<target.count + 1 {
        var newTarget = target
        let atIndex = String.Index(encodedOffset: i)
        
        // Note: We can insert at the end of a list which
        // will append our character rather than throw
        // an exception
        newTarget.insert(newChar, at: atIndex)
        distribution.append(newTarget)
    }
    return distribution
}

var word = "LINK"
let perms = permutations(source: word)

// Ensure we're didn't create any dupe permutations
var permsMap = [String:Int]()

for perm in perms {
    if let permCount = permsMap[perm] {
        permsMap[perm] = permCount + 1
    } else {
        permsMap[perm] = 1
    }
}

assert(permsMap.keys.count == perms.count)