¿Cómo generar todas las combinaciones posibles?

Actualmente estoy tratando de hacer un Set de todas las combinaciones posibles de una Array de Strings , si cada elemento contiene solo una letra.

La Array sí misma puede contener la misma letra dos veces o incluso más, y solo se deben usar tan a menudo como ocurran.

El Set debería contener más tarde todas las combinaciones desde un mínimo de 2 letras hasta la longitud de la Array dada.

Busqué aquí en stackoverflow, pero solo encontré funciones de permutación que ignoran el hecho, que cada letra debe usarse solo con la frecuencia que ocurra.

Este es mi primer proyecto de Swift 2, así que por favor, perdonen mi greenhorn-ness 🙂

Lo que quiero

 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 ... 

Mi enfoque actual

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

Lo sé, esto es terriblemente incorrecto de muchas maneras, pero estoy atascado con este código, y no sé cómo agregar una funcionalidad recursiva.

Prueba esto.

El algorithm general es tener una fromList contenga las letras que aún no ha utilizado y una toList que es la cadena que ha creado hasta ahora. Esto usa la recursion para build todas las cadenas posibles y las agrega al set cuando la longitud es 2 o mayor:

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

Respuesta más rápida:

Como señaló @MartinR en su publicación, la solución anterior es un poco lenta debido a la creación y copy de sets. Originalmente había escrito esto usando una variable inout para el set, pero lo cambié a la interfaz más funcional para que sea agradable llamar.

Aquí está mi implementación original (más rápida), más la permute en una permute que toma solo un [String] y devuelve un Set<String> . Realiza el trabajo de crear el set y la matriz toList y luego llama a la versión interna de permute para hacer el trabajo real:

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

Editar: agregué un parámetro minStringLen (con el valor pnetworkingeterminado de 2 ) en lugar de codificar el valor.

Consulte la respuesta de @ MartinR para las comparaciones de desempeño.

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 } 

Esto es bastante similar a la respuesta de @ vacawama, pero con suerte es lo suficientemente diferente como para merecer una respuesta por separado 🙂

Aquí, se crea una matriz con todas las combinaciones (explicando los comentarios en línea):

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

Luego puede filtrar las cadenas con al less dos letras y convertirlas en un 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"] 

Hice una comparación de performance simple (comstackda en modo Liberación en un 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)) 

El resultado depende del tamaño de la matriz de input, pero el método actualizado de @ vacawama es el más rápido:

 # of array Este vacawama's vacawama's
 elementos: método: primer método: segundo método:

   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

Aquí hay una function Swift 3 que es un poco más rápida. Se basa en una extensión del tipo de matriz que se puede usar en matrices con cualquier tipo de elemento.

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

En mis testings, funcionó aproximadamente 40 veces más rápido que la segunda versión de vacawama en 7 letras.

[EDIT] Me di count más tarde de que esta function produce combinaciones (como se solicitó en el OP) donde la function vacawama produce permutaciones. Probé un algorithm equivalente para permutaciones y fue simplemente 55% más rápido que el de 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 } } 

En su ejemplo de salida, no estaba claro lo que realmente desea, ya sea:

  1. todas las combinaciones y permutaciones de ellos:

     ["AB", "BA", "AC", "CA", "AD", "DA", ..., "ABCD", "ABDC", "ACBD", "ACDB", ...] 
  2. solo todas las combinaciones:

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

Puedo recomendar la gran librería Swift de @ oisdk: SwiftSequence para ambos, tiene muchas funciones útiles. En la sección Combinaciones, incluso muestra un ejemplo de su uso con Power Set , que es casi exactamente lo que está buscando en el caso 1. Al importar los files de su biblioteca, puede crear la function powerSet en CollectionType s como esta :

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

Este método evalúa perezosamente, lo que significa que solo se evalúa cuando realmente lo necesita. Ahora mencionaste que solo quieres tener combinaciones de al less 2 elementos. Esto se hace fácilmente con el método de 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"]] 

Para el caso 2. donde también necesita permutaciones de esos, puede hacer esto:

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

Puede convertirlos a un Set de String o a una Array :

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

Pero recomiendo utilizar la versión perezosa;) Y sí, para eliminar duplicates, puede usar Set(["A", "B", "C", "D"]) lugar de solo ["A", "B", "C", "D"]

También puede hacer el caso 2. de una vez así:

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