Algorithms: No Repeats Please in Swift

Subscribe to my newsletter and never miss my upcoming articles

Hello ladies and gentlemen, Leo here.

Today we'll continue the series Algorithms, the Final Frontier. Always remember, this is ONE of many possible solution for the problem. The challenge is here: Link to Challenge

Let's go!

The problem: Return the number of total permutations of the provided string that don't have repeated consecutive letters. Assume that all characters in the provided string are each unique. For example, aab should return 2 because it has 6 total permutations (aab, aab, aba, aba, baa, baa), but only 2 of them (aba and aba) don't have the same letter (in this case a) repeating.

Solution:

var input = "aab"
var charArray = Array(input)
var result : [String] = []

func wirthPermutation(_ charArray: [Character], _ n: Int) {
    if n == 0 {
        let actualPermutation = String(charArray)
        if actualPermutation.range(of: #"([\w])\1"#, options: .regularExpression) == nil {
            result.append(actualPermutation)
        }
    } else {
        var b = charArray
        wirthPermutation(b, n - 1)
        for i in 0..<n {
            b.swapAt(i, n)
            wirthPermutation(b, n - 1)
            b.swapAt(i, n)
        }
    }
}

wirthPermutation(charArray, charArray.count-1) //  have to call it with array count minus one
print(result)

You should be asking yourself "Why Wirth permutation?", because the inventor of this recursive algorithm is Nikalus Wirth the legendary Swiss computer scientist.

Thanks for the reading and... That's all folks!

No Comments Yet