如何生成所有可能的组合?

我目前正在尝试从一个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 。 它完成创buildsettoList数组的工作,然后调用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 } } 

在你的输出例子中,你并不清楚你真正想要的是什么:

  1. 他们的所有组合和排列:

     ["AB", "BA", "AC", "CA", "AD", "DA", ..., "ABCD", "ABDC", "ACBD", "ACDB", ...] 
  2. 只是所有的组合:

     ["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("") })