How to create all possible combinations?

Question

I'm currently trying to Set all possible combinations from Array of Strings , each element contains only one letter.

Array itself may contain the same letter twice or more, and should only be used as often as they occur.

Set must contain all combinations from at least two letters to the length of the specified Array .

I searched here on stackoverflow, but found only permutation functions that ignore the fact that each letter should only be used as often as they happen.

This is my first Swift 2 project, so please forgive my philology :)

What I want

 var array = ["A", "B", "C","D"] var combinations: Set<String> ... <MAGIC> ... print(combinations) // "AB", "ABC", "ABD", "ABCD", "ABDC", "AC", "ACB", "ACD", "ACBD", "ACDB", and so on ... 

My current approach

 func permuation(arr: Array<String>) { for (index, elementA) in arr.enumerate() { //1..2..3..4 var tmpString = elementA var tmpArray = arr tmpArray.removeAtIndex(index) for (index2, elementB) in tmpArray.enumerate() { // 12..13..14 var tmpString2 = tmpString + elementB var tmpArray2 = tmpArray //[3,4] tmpArray2.removeAtIndex(index2) results.append(tmpString2) } } } permuation(array) print(results) // "["AB", "AC", "AD", "BA", "BC", "BD", "CA", "CB", "CD", "DA", "DB", "DC"]" 

I know this is so terribly wrong in many ways, but I am stuck in this code and don't know how to add recursive functionality.

Answer 1

Try it.

The general algorithm is to have fromList containing letters that you have not used yet, and toList is the string that you have created so far. This uses recursion to create all possible strings and adds them to the set when the length is 2 or more:

 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"} 

---

Quick response:

As @MartinR noted in his post, the solution above is a bit slow due to the whole creation and copying of sets. I originally wrote this using the inout variable for set, but changed it to a more functional interface to make the call nice.

Here is my original (faster) implementation, plus I built it into permute , which takes just [String] and returns Set<String> . It does the work of creating an array of set and toList , and then calls the internal 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 the minStringLen parameter (with a default value of 2 ) instead of hard-coding this value.

See @MartinR answer for performance comparison.

---

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"] 

Answer 2

This is very similar to @vacawama's answer, but hopefully different enough to deserve a separate answer :)

This creates an array with all the combinations (explaining inline comments):

 func combinations(array : [String]) -> [String] { // Recursion terminates here: if array.count == 0 { return [] } // Concatenate all combinations that can be built with element #i at the // first place, where i runs through all array indices: return array.indices.flatMap { i -> [String] in // Pick element #i and remove it from the array: var arrayMinusOne = array let elem = arrayMinusOne.removeAtIndex(i) // Prepend element to all combinations of the smaller array: return [elem] + combinations(arrayMinusOne).map { elem + $0 } } } 

Then you can filter the strings with at least two letters, and convert it to Set :

 let c = Set(combinations(["A", "B", "C"]).filter { $0.characters.count >= 2 }) print(c) // ["BA", "AC", "ABC", "AB", "BCA", "CB", "BC", "CAB", "ACB", "CA", "CBA", "BAC"] 

I made a simple performance comparison (compiled in Release mode on Macbook Pro):

 let array = ["A", "B", "C", "D", "E", "F", "G"] let t1 = NSDate() let c1 = Set(combinations(array).filter { $0.characters.count >= 2 }) let t2 = NSDate() let c2 = permute(array) let t3 = NSDate() print(c1 == c2) // true print(t2.timeIntervalSinceDate(t1)) print(t3.timeIntervalSinceDate(t2)) 

The result depends on the size of the input array, but the updated @vacawama method is the fastest:

 # of array This vacawama vacawama's
 elements: method: 1st method: 2nd method:

   2 0.00016 0.00005 0.00001
   3 0.00043 0.00013 0.00004
   4 0.00093 0.00062 0.00014
   5 0.00335 0.00838 0.00071
   6 0.01756 0.24399 0.00437
   7 0.13625 11.90969 0.03692

Answer 3

Here's the Swift 3 feature, which is slightly faster. It is based on an extension of type Array, which can be used on arrays with any type of element.

 public func allCombinations(_ array:[String], minLength:Int=2) -> [String] { var result:[String] = [] for n in minLength...array.count { result = result + array.combinations(of:n).map{ $0.joined(separator:"") } } return result } extension Array { public func combinations(of group:Int) -> [[Element]] { if group > count { return [] } if group == count { return [self] } var result:[[Element]] = [] var comboIndexes = (0..<group).map{$0} let fullCombo = group - 1 let indexLimit = count - fullCombo var carry = fullCombo while carry >= 0 { if carry == fullCombo { result.append(comboIndexes.map{self[$0]}) } comboIndexes[carry] += 1 if comboIndexes[carry] == carry + indexLimit { carry -= 1 ; continue } while carry < fullCombo { carry += 1 comboIndexes[carry] = comboIndexes[carry-1] + 1 } } return result } } 

In my tests, it worked about 40 times faster than the second vacawama version of 7 letters.

[EDIT] I later realized that this function produces combinations (as requested by the OP), where the vacawama function produces permutations. I tested the equivalent permutation algorithm, and it was only 55% faster than vacawama.

 extension Array { public func permutations(of group:Int? = nil) -> [[Element]] { let group = group ?? count var result : [[Element]] = [] var permutation : [Element] = [] func permute(from baseIndex:Int) { if baseIndex == permutation.count - 1 { result.append(permutation) return } permute(from:baseIndex+1) for index in baseIndex+1..<permutation.count { swap(&permutation[baseIndex],&permutation[index]) permute(from:baseIndex+1) } let baseElement = permutation[baseIndex] permutation.remove(at:baseIndex) permutation.append(baseElement) } var comboIndexes = (0..<group).map{$0} let fullCombo = group - 1 let indexLimit = count - fullCombo var carry = fullCombo while carry >= 0 { if carry == fullCombo { permutation = comboIndexes.map{self[$0]} permute(from:0) } comboIndexes[carry] += 1 if comboIndexes[carry] == carry + indexLimit { carry -= 1 ; continue } while carry < fullCombo { carry += 1 comboIndexes[carry] = comboIndexes[carry-1] + 1 } } return result } } 

Answer 4

In your output example, it was not entirely clear what you really want:

• all combinations and their permutations:

   ["AB", "BA", "AC", "CA", "AD", "DA", ..., "ABCD", "ABDC", "ACBD", "ACDB", ...] 

• just all the combinations:

   ["AB", "AC", "AD", "BC", "BD", "CD", "ABC", "ABD", ...] 

I can recommend @oisdk a large Swift library: SwiftSequence for them, it has many useful features. In the Combinations section, he even shows an example of its use with the Power Set , which you almost certainly look for in case 1. When importing files from his library, you can create the powerSet function on CollectionType as follows:

 extension CollectionType { func powerSet() -> LazySequence<FlattenSequence<LazyMapSequence<Self, ComboSeq<Self.Generator.Element>>>>{ var i = 0 return lazy.flatMap{ _ in self.lazyCombos(++i) } } } 

This method is evaluated lazily, which means that it is only evaluated when it really needs to. Now you have mentioned that you only want to have combinations of at least two elements. This is easily done using the filter method:

 let combinations = ["A", "B", "C", "D"].powerSet().filter{ $0.count >= 2 } // As an array: [["A", "B"], ["A", "C"], ["A", "D"], ["B", "C"], ["B", "D"], ["C", "D"], ["A", "B", "C"], ["A", "B", "D"], ["A", "C", "D"], ["B", "C", "D"], ["A", "B", "C", "D"]] 

In case 2., where you also need permutations, you can do this:

 let combPerms = combinations.flatMap{ $0.permutations() } // As an array: [["A", "B"], ["B", "A"], ["A", "C"], ["C", "A"], ["A", "D"], ["D", "A"], ["B", "C"], ["C", "B"], ["B", "D"], ["D", "B"], ["C", "D"], ["D", "C"], ["A", "B", "C"], ["A", "C", "B"], ["B", "A", "C"], ["B", "C", "A"], ["C", "A", "B"], ["C", "B", "A"], ["A", "B", "D"], ["A", "D", "B"], ["B", "A", "D"], ["B", "D", "A"], ["D", "A", "B"], ["D", "B", "A"], ["A", "C", "D"], ["A", "D", "C"], ["C", "A", "D"], ["C", "D", "A"], ["D", "A", "C"], ["D", "C", "A"], ["B", "C", "D"], ["B", "D", "C"], ["C", "B", "D"], ["C", "D", "B"], ["D", "B", "C"], ["D", "C", "B"], ["A", "B", "C", "D"], ["A", "B", "D", "C"], ["A", "C", "B", "D"], ["A", "C", "D", "B"], ["A", "D", "B", "C"], ["A", "D", "C", "B"], ["B", "A", "C", "D"], ["B", "A", "D", "C"], ["B", "C", "A", "D"], ["B", "C", "D", "A"], ["B", "D", "A", "C"], ["B", "D", "C", "A"], ["C", "A", "B", "D"], ["C", "A", "D", "B"], ["C", "B", "A", "D"], ["C", "B", "D", "A"], ["C", "D", "A", "B"], ["C", "D", "B", "A"], ["D", "A", "B", "C"], ["D", "A", "C", "B"], ["D", "B", "A", "C"], ["D", "B", "C", "A"], ["D", "C", "A", "B"], ["D", "C", "B", "A"]] 

You can convert them to Set from String or Array :

 let array = Array(combPerms) let set = Set(combPerms) 

But I highly recommend using the lazy version;) And yes, to remove duplicates, you can just use Set(["A", "B", "C", "D"]) instead of just ["A", "B", "C", "D"]

You can also make case 2. in one move as follows:

 let x = ["A", "B", "C", "D"] let result = Set( x.indices .flatMap{ x.lazyCombos($0 + 1) } .filter{ $0.count >= 2 } .flatMap{ $0.permutations() } .map{ $0.joinWithSeparator("") })