How can I find all capitalization combinations of a String in Swift?

Question

Problem

I'm trying to find all of the possible combinations of capitalization for a String in Swift. For example, given the String "abc", I would want my method to return an Array of Strings, like this: ["Abc", "aBc", "abC", "ABc", "abc", "ABC", "aBC", "AbC"]. The formula for the possible number of capitalization combinations is like this:

2ⁱ

where i is the number of Characters in the String.

Attempted Solutions

I've tried the following function, via an extension to the String type:

extension String {
func allPossibleCombinations() -> [String] {
        let string = self
        var result = [String]()
        var current = string
        result.append(current)
        for i in 0..<string.count {
            let index = string.index(string.startIndex, offsetBy: i)
            if string[index].isLetter {
                current = current.replacingCharacters(in: index...index, with: String(current[index]).uppercased())
                result.append(current)
            }
        }
        return result
    }

}

This didn't work because it only returns capitalizations in order. For example, if I were to call this method on the String "abc", it would return

["abc", "Abc", "ABc", "ABC"]

This should produce, as stated above, 8 different Strings. I suspect that I need to factor in an exponent to my code, or potentially some form of randomly choosing a Character.

Summary

I am trying to make a function to get all possible capitalization forms of a String. I have a current attempt, but it is not sufficient as it does not produce all possible options.

vacawama · Accepted Answer · 2022-12-04T23:37:38.220

Compute the integers in the range 0 ..< 2^length and use the bits of the binary representation to tell you when to capitalize a letter:

extension String {
    func allPossibleCombinations() -> [String] {
        guard self.count > 0 else { return [] }
        var result = [String]()
        let lower = self.lowercased().map(String.init)
        let upper = self.uppercased().map(String.init)
        let length = self.count
        let limit = 1 << length
        for n in 0..<limit {
            var word = ""
            for i in 0..<length {
                if n & (1 << (length - i - 1)) != 0 {
                    word += upper[i]
                } else {
                    word += lower[i]
                }
            }
            result.append(word)
        }
        return result
    }
}

Examples

print("abc".allPossibleCombinations())

// ["abc", "abC", "aBc", "aBC", "Abc", "AbC", "ABc", "ABC"]

print("abcd".allPossibleCombinations())

// ["abcd", "abcD", "abCd", "abCD", "aBcd", "aBcD", "aBCd", "aBCD", "Abcd", "AbcD", "AbCd", "AbCD", "ABcd", "ABcD", "ABCd", "ABCD"]

Alex's Swifty Version

In the comments, Alex added this Swifty version using nested maps:

extension String {
    func allPossibleCombinations() -> [String] {
        guard self.count > 0 else { return [] }

        let length = self.count
        let limit = 1 << self.count
        
        return (0..<limit) .map { n in
            return self.enumerated()
                .map { i, c in (n & (1 << (length - i - 1)) != 0) ? c.uppercased() : c.lowercased() }
                .joined()
        }
    }
}

I think you can replace a chunk of this with a `map` call: https://gist.github.com/amomchilov/6ba89e4641b12798b9c472e6f930c8e2 — Alexander, Dec 04 '22 at 23:15

score 0 · Answer 2 · answered Dec 05 '22 at 01:05

Use uniquePermutations.

import Algorithms

extension String {
  var capitalizationCombinations: [Self] {
    [false, true].flatMap {
      capitalize in repeatElement(capitalize, count: count)
    }
    .uniquePermutations(ofCount: count)
    .map { [lowercased = lowercased()] capitalizes in
      .init(
        zip(lowercased, capitalizes).map { character, capitalize in
          capitalize ? character.uppercased().first! : character
        }
      )
    }
  }

score 0 · Answer 3 · answered Dec 05 '22 at 02:06

You could follow a recursive approach:

func capitalizations(of string: String) -> [String] {
    guard let first = string.first else { return [] }

    let firstLowercase = first.lowercased()
    let firstUppercase = first.uppercased()

    if string.count == 1 {
        return [firstLowercase, firstUppercase]
    } else {
        let partial = capitalizations(of: String(string.dropFirst()))
        return partial.map { firstLowercase + $0 } + partial.map { firstUppercase + $0 }
    }
}

print(capitalizations(of: "abc"))
// ["abc", "abC", "aBc", "aBC", "Abc", "AbC", "ABc", "ABC"]

Just take the first character, lowercase and uppercase it, and prepend it to capitalizations for the rest of the string.

Interestingly, after testing all three answers, this one is the fastest. Thank you for this answer! — , Dec 05 '22 at 03:27