Jak wygenerować wszystkie możliwe kombinacje?

Question

Obecnie próbuję utworzyć Set wszystkich możliwych kombinacji z Array z Strings, gdy każdy element zawiera tylko jedną literę.

Sam w sobie może zawierać tę samą literę dwa razy lub nawet więcej i powinny one być używane tak często, jak się pojawią.

Później Set powinien zawierać wszystkie kombinacje od minimum 2 liter do długości podanego Array.

Szukałem tutaj na stackoverflow, ale tylko znaleziono funkcje permutacji, które ignorują fakt, że każda litera powinna być używana tak często, jak się pojawiają.

To mój pierwszy Swift 2 projekt, więc proszę wybaczyć mój greenhornish-ności :)

Co chcę

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

Moje obecne podejście

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 Wiem, że jest tak strasznie źle na tak wiele sposobów, ale utknąłem z tym kodem i nie wiem jak dodać funkcję rekursywną.

Answer 1

Spróbuj tego.

Ogólny algorytm polega na tym, aby mieć fromList zawierający litery, których jeszcze nie używałeś, oraz toList, który jest struną, którą stworzyłeś do tej pory. To używa rekursji do budowania wszystkich możliwych ciągów i dodaje je do zestawu, gdy długość wynosi 2 lub wyższa:

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

---

Szybsze Odpowiedź:

Jak @MartinR podkreślił w swoim stanowisku powyższe rozwiązanie jest nieco powolne ze względu na tworzenie i kopiowanie zestawów. Pierwotnie napisałem to za pomocą zmiennej inout dla zestawu, ale zmieniłem ją na bardziej funkcjonalny interfejs, aby ułatwić wywoływanie.

Oto moja oryginalna (szybsza) implementacja, a także osadzona w permute, która zajmuje tylko [String] i zwraca Set<String>. Czyni pracę tworząc set i tablicę toList a następnie wywołuje wewnętrzną wersję permute zrobić prawdziwą pracę:

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: dodałem parametr minStringLen (z domyślnej wartości 2) zamiast twardego kodowania tej wartości.

Zobacz odpowiedź @ MartinR na porównanie wydajności.

---

Swift 3 i 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

ta jest bardzo podobna do użytkownika @ vacawama odpowiedź, ale mam nadzieję, że różni na tyle, że zasługuje na osobny odpowiedź :)

Tutaj tablica z kombinacjami wszystkie jest zbudowany (objaśnienie komentarze wbudowane):

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

Następnie można filtrować za sznurki z co najmniej dwóch liter, a przekonwertować go na 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"] 

Zrobiłem proste porównanie wydajności (skompilowany w trybie Release na 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)) 

wynik zależy od wielkości tablicy wejściowej, zaktualizowane metoda ale @ vacawama jest najszybszym:

 
# of array This  vacawama's 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

W przykładzie wyjścia nie było jasne, co naprawdę chcesz, albo:

1. wszystkie kombinacje i permutacje z nich:

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

2. zaledwie wszystkich kombinacjach:

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

Mogę polecić wspaniałą bibliotekę Swift @ Oisdk: SwiftSequence dla obu z nich, ma wiele przydatnych funkcji. W sekcji Kombinacje pokazuje nawet przykład jego użycia z Power Set, który jest niemal dokładnie tym, czego szukasz w przypadku 1. Po zaimportowaniu plików z jego biblioteki, możesz utworzyć funkcję powerSet na CollectionType s w ten sposób:

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

Metoda ta ocenia leniwie, co oznacza, że ​​jest oceniana tylko wtedy, gdy naprawdę tego potrzebuje. Teraz wspomniałeś, że chcesz mieć tylko kombinacje co najmniej 2 elementów. Można to łatwo zrobić za pomocą metody 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"]] 

Dla przypadku 2.gdzie trzeba permutacje tych, jak dobrze, można to zrobić:

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

Można konwertować je do Set o String s lub Array:

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

Ale gorąco polecam używać leniwy wersja;) A tak, aby usunąć duplikaty można po prostu użyć Set(["A", "B", "C", "D"]) zamiast tylko ["A", "B", "C", "D"]

można również zrobić przypadek 2. za jednym razem tak:

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

Answer 4

Oto funkcja Swift 3, która jest nieco szybsza. Opiera się on na rozszerzeniu typu Array, które może być używane na tablicach z dowolnym typem elementu.

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

W moich testach przebiegała około 40 razy szybciej niż druga wersja vacawama na 7 literach.

[EDYCJA] Zdałem sobie sprawę później, że funkcja ta tworzy kombinacje (zgodnie z wnioskiem w PO), gdzie funkcja vacawama tworzy permutacje. Przetestowałem równoważny algorytm dla permutacji i było to tylko 55% szybciej niż 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 
    } 
}