如何生成所有可能的组合？
我目前正在尝试从一个Strings Array中创build一个所有可能组合的Set ，每个元素只包含一个字母。
Array本身可以包含相同的字母两次或甚至更多，他们应该只发生在经常使用。
该Set稍后将包含从至less2个字母到给定Array长度的所有组合。
我在这里search了stackoverflow，但只发现忽略事实的排列函数，每个字母应该只发生在经常使用。
这是我第一个Swift 2项目，所以请原谅我greenhornish性格:)
我想要的是
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 ...
我目前的做法
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"]"
我知道，在很多方面这是非常错误的，但我坚持这个代码，并不知道如何添加recursionfunction。
尝试这个。
一般的algorithm是有一个包含你还没有使用过的字母的toList和一个toListbuild立的stringtoList 。 这使用recursion构build所有可能的string，并在长度为2或更大时将它们添加到集合中：
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"}
更快答案：
正如@MartinR在他的文章中指出的那样，上面的解决scheme由于所有的集合的创build和复制都有点慢。 我最初使用一个inoutvariables来编写它，但将其更改为更多function的接口，以便调用它。
这是我原来的（更快）的实现，加上我把它embedded一个只需要一个[String]并返回一个Set<String>的permute 。 它完成创buildset和toList数组的工作，然后调用permute的内部版本来完成真正的工作：
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"}
编辑：我添加了一个minStringLen参数（默认值为2 ），而不是硬编码该值。
请参阅@ MartinR的性能比较答案。
Swift 3和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"]
这与@ vacawama的答案很相似，但希望不同，它值得一个单独的答案:)
在这里，build立了一个包含所有组合的数组（解释内联注释）：
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 } } }
然后你可以用至less两个字母过滤string，并将其转换为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"]
我做了一个简单的性能比较（编译在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))
结果取决于input数组的大小，但@ vacawama的更新方法是最快的：
数组＃这是vacawama的vacawama的 元素：方法：第一种方法：第二种方法： 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
这是一个快一点的Swift 3函数。 它基于数组types的扩展，可以在任何元素types的数组上使用。
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 } }
在我的testing中，它的速度比vacawama在7个字母上的第二个版本快40倍。
[编辑]我后来意识到，这个函数产生的组合（在OP中的要求）vacawama函数产生排列。 我testing了一个等同的排列algorithm，它只比vacawama快55％。
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 } }
在你的输出例子中，你并不清楚你真正想要的是什么：
-
他们的所有组合和排列：
["AB", "BA", "AC", "CA", "AD", "DA", ..., "ABCD", "ABDC", "ACBD", "ACDB", ...] -
只是所有的组合：
["AB", "AC", "AD", "BC", "BD", "CD", "ABC", "ABD", ...]
我可以推荐@ oisdk伟大的Swift库： SwiftSequence ，它们都有很多有用的function。 在“组合”部分，他甚至展示了一个使用Power Set的例子，它几乎就是你在情况1中所要查找的内容。一旦导入了库的文件，你就可以在CollectionType上创buildpowerSet函数：
extension CollectionType { func powerSet() -> LazySequence<FlattenSequence<LazyMapSequence<Self, ComboSeq<Self.Generator.Element>>>>{ var i = 0 return lazy.flatMap{ _ in self.lazyCombos(++i) } } }
这种方法懒惰地评估，这意味着它只在真正需要的时候才被评估。 现在你提到你只想要有至less两个元素的组合。 这很容易filter方法完成：
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"]]
对于情况2，你需要排列这些，你可以这样做：
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"]]
您可以将它们转换为一Set String或一个Array ：
let array = Array(combPerms) let set = Set(combPerms)
但我强烈build议使用懒惰版本;）是的，删除重复，你可以使用Set(["A", "B", "C", "D"])而不是只是["A", "B", "C", "D"]
你也可以这样做：
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("") })