Calculate All Permutations of a String in Swift

swift string permutations allowing the same strings

In another question, you ask how to filter the results from dfri's answer (+1) to prune out duplicates resulting from a different order of elements (e.g. if you got a result set with "AAB", "ABA", and "BAA", prune out the latter two).

If that's what you want to do, I'd suggest writing a function that just returned that set of solutions directly:

extension Array where Element: StringProtocol {

    /// Return combinations of the elements of the array (ignoring the order of items in those combinations).
    ///
    /// - Parameters:
    ///   - size: The size of the combinations to be returned.
    ///   - allowDuplicates: Boolean indicating whether an item in the array can be repeated in the combinations (e.g. is the sampled item returned to the original set or not).
    ///
    /// - Returns: A collection of resulting combinations.

    func combinations(size: Int, allowDuplicates: Bool = false) -> [String] {
        let n = count

        if size > n && !allowDuplicates { return [] }

        var combinations: [String] = []

        var indices = [0]

        var i = 0

        while true {
            // build out array of indexes (if not complete)

            while indices.count < size {
                i = indices.last! + (allowDuplicates ? 0 : 1)
                if i < n {
                    indices.append(i)
                }
            }

            // add combination associated with this particular array of indices

            combinations.append(indices.map { self[$0] }.joined())

            // prepare next one (incrementing the last component and/or deleting as needed

            repeat {
                if indices.count == 0 { return combinations }
                i = indices.last! + 1
                indices.removeLast()
            } while i > n - (allowDuplicates ? 1 : (size - indices.count))
            indices.append(i)
        }
    }
}

Thus:

let array = ["A", "B", "C", "D"]
let result = array.combinations(size: 2, allowDuplicates: true)

would return:

["AA", "AB", "AC", "AD", "BB", "BC", "BD", "CC", "CD", "DD"]

And if you didn't want it to allow duplicates:

let result = array.combinations(size: 2)

would return:

["AB", "AC", "AD", "BC", "BD", "CD"]

This approach would avoid needing to later filter the results.

Note, I'm sure there are more elegant ways to achieve the above, but hopefully this illustrates the basic idea.

Printing out all the combinations of a string

Not a direct answer to your question but you can get all permutations (translated from java to Swift) as follow:

public extension RangeReplaceableCollection {
    func permutations() -> [SubSequence] {
        isEmpty ? [] : permutate(.init())
    }
    private func permutate(_ subSequence: SubSequence) -> [SubSequence] {
        var permutations = isEmpty ? [subSequence] : []
        indices.forEach {
            permutations += (self[..<$0] + self[$0...].dropFirst())
                .permutate(subSequence + CollectionOfOne(self[$0]))
        }
        return permutations
    }
}

---

let str = "ABCD"
print(str.permutations())   // "["ABCD", "ABDC", "ACBD", "ACDB", "ADBC", "ADCB", "BACD", "BADC", "BCAD", "BCDA", "BDAC", "BDCA", "CABD", "CADB", "CBAD", "CBDA", "CDAB", "CDBA", "DABC", "DACB", "DBAC", "DBCA", "DCAB", "DCBA"]\n"

---

Per-mutating a substring

print("ABCD".dropLast().permutations())   // ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]\n"

How to generate all possible combinations?

Try this.

The general algorithm is to have a fromList containing the letters you haven't used yet and a toList that is the string you've built up so far. This uses recursion to build up all possible strings and adds them to the set when the length is 2 or greater:

func permute(fromList: [String], toList: [String] = [String](), var set: Set<String> = Set<String>()) -> Set<String> {
    if toList.count >= 2 {
        set.insert(toList.joinWithSeparator(""))
    }
    if !fromList.isEmpty {
        for (index, item) in fromList.enumerate() {
            var newFrom = fromList
            newFrom.removeAtIndex(index)
            set = permute(newFrom, toList: toList + [item], set: set)
        }
    }
    return set
}

permute(["A", "B", "C"])
// {"BA", "AC", "ABC", "AB", "BCA", "CB", "BC", "CAB", "ACB", "CA", "CBA", "BAC"}

permute(["A", "A", "B"])
// {"BA", "BAA", "AAB", "AB", "ABA", "AA"}

---

Faster Answer:

As @MartinR pointed out in his post, the solution above is a little slow because of all of the creation and copying of sets. I had originally written this using an inout variable for set, but changed it to the more functional interface to make it nice to call.

Here is my original (faster) implementation, plus I embedded it in a permute that takes just an [String] and returns a Set<String>. It does the work of creating the set and the toList array and then calls the inner version of permute to do the real work:

func permute(list: [String], minStringLen: Int = 2) -> Set<String> {
    func permute(fromList: [String], toList: [String], minStringLen: Int, inout set: Set<String>) {
        if toList.count >= minStringLen {
            set.insert(toList.joinWithSeparator(""))
        }
        if !fromList.isEmpty {
            for (index, item) in fromList.enumerate() {
                var newFrom = fromList
                newFrom.removeAtIndex(index)
                permute(newFrom, toList: toList + [item], minStringLen: minStringLen, set: &set)
            }
        }
    }

    var set = Set<String>()
    permute(list, toList:[], minStringLen: minStringLen, set: &set)
    return set
}

permute(["A", "B", "C"])
// {"BA", "AC", "ABC", "AB", "BCA", "CB", "BC", "CAB", "ACB", "CA", "CBA", "BAC"}

permute(["A", "A", "B"])
// {"BA", "BAA", "AAB", "AB", "ABA", "AA"}

permute(["A", "A", "B"], minStringLen: 1)
// {"BA", "A", "BAA", "AB", "AA", "B", "AAB", "ABA"}

permute(["A", "A", "B"], minStringLen: 3)
// {"ABA", "BAA", "AAB"}

Edit:
I added a minStringLen parameter (with default value of 2) instead of hard coding that value.

See @MartinR's answer for performance comparisons.

---

Swift 3 and Swift 4:

func permute(list: [String], minStringLen: Int = 2) -> Set<String> {
    func permute(fromList: [String], toList: [String], minStringLen: Int, set: inout Set<String>) {
        if toList.count >= minStringLen {
            set.insert(toList.joined(separator: ""))
        }
        if !fromList.isEmpty {
            for (index, item) in fromList.enumerated() {
                var newFrom = fromList
                newFrom.remove(at: index)
                permute(fromList: newFrom, toList: toList + [item], minStringLen: minStringLen, set: &set)
            }
        }
    }

    var set = Set<String>()
    permute(fromList: list, toList:[], minStringLen: minStringLen, set: &set)
    return set
}

print(permute(list: ["A", "B", "C"]))
// ["ABC", "CA", "BAC", "ACB", "BA", "CAB", "BC", "CB", "BCA", "CBA", "AB", "AC"]

print(permute(list: ["A", "A", "B"]))
// ["AA", "AAB", "ABA", "AB", "BA", "BAA"]

print(permute(list: ["A", "A", "B"], minStringLen: 1))
// ["AAB", "ABA", "B", "BA", "A", "BAA", "AA", "AB"]

print(permute(list: ["A", "A", "B"], minStringLen: 3))
// ["AAB", "ABA", "BAA"]

How to generate all permutations of 1 and 0 bits of a given size in Swift

Just for fun a functional approach:

extension RangeReplaceableCollection {
    var combinations: [Self] { generate(2) }
    func generate(_ n: Int) -> [Self] {
        repeatElement(self, count: n).reduce([.init()]) { result, element in
            result.flatMap { elements in
                element.map { elements + CollectionOfOne($0) }
            }
        }
    }
}

---

Usage:

let elements = [false, true]  // [false, true]
let combinations = elements.combinations  // [[false, false], [false, true], [true, false], [true, true]]
let generateThree = elements.generate(3)  // [[false, false, false], [false, false, true], [false, true, false], [false, true, true], [true, false, false], [true, false, true], [true, true, false], [true, true, true]]

or

let elements = [0, 1]  // [0, 1]
let combinations = elements.combinations  // [[0, 0], [0, 1], [1, 0], [1, 1]]
let generateThree = elements.generate(3)  // [0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

or with Strings (Collection Of Characters):

let elements = "01" // "01"
let combinations = elements.combinations  // ["00", "01", "10", "11"]
let generateThree = elements.generate(3)  // ["000", "001", "010", "011", "100", "101", "110", "111"]

Find all combination of string array in swift

@yannick's answer is very close.

By computing a Power Set of your set, you obtain all the possible subsets (including your original set and the empty set).

Once you have obtained the Power Set, all you have to do is join the subsets into a single string in order to obtain the result that you're looking for.

Here's the complete solution (along with updated code and plenty of comments):

extension Array {
    var powerset: [[Element]] {
        guard count > 0 else {
            return [[]]
        }

        // tail contains the whole array BUT the first element
        let tail = Array(self[1..<endIndex])

        // head contains only the first element
        let head = self[0]

        // computing the tail's powerset
        let withoutHead = tail.powerset

        // mergin the head with the tail's powerset
        let withHead = withoutHead.map { $0 + [head] }

        // returning the tail's powerset and the just computed withHead array
        return withHead + withoutHead
    }
}

let myArray = ["A", "B", "C", "D"]
print(myArray.powerset) // -> [["D", "C", "B", "A"], ["C", "B", "A"], ["D", "B", "A"], ["B", "A"], ["D", "C", "A"], ["C", "A"], ["D", "A"], ["A"], ["D", "C", "B"], ["C", "B"], ["D", "B"], ["B"], ["D", "C"], ["C"], ["D"], []]

// joining the subsets
let myResult = myArray.powerset.map { $0.sort().joinWithSeparator("") }
print(myResult) // -> ["A", "AB", "ABC", "ABCD", "ABD", "AC", "ACD", "AD", "B", "BC", "BCD", "BD", "C", "CD", "D", ""]

PS

Note that this solution uses a recursive approach, while yours was using an iterative approach.

PPS

If you don't want the empty string "" in your solution, you can just filter it away:

let myResult = myArray.powerset.map({ $0.sort().joinWithSeparator("") }).filter({ $0 != "" })

print(myResult) // -> ["A", "AB", "ABC", "ABCD", "ABD", "AC", "ACD", "AD", "B", "BC", "BCD", "BD", "C", "CD", "D"]

How to generate combinations of r elements in a given array of size n in swift?

Actually the total permutation pairs are

[[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]

There's no need to reinvent the wheel. Apple provides a collection of useful and optimized algorithms.

Add the package Swift Algorithms to your project

Then write

import Algorithms

let array = [1, 2, 3, 4]
    
let permutations = array.permutations(ofCount: 2)
print(Array(permutations), permutations.count)

Generating all permutations of a given string

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

(via Introduction to Programming in Java)

---

Related Topics