Как сгенерировать все возможные комбинации?

Question

Я сейчас пытаюсь сделать Set из всех возможных комбинаций из Array из Strings, каждый из которых содержит только одну букву.

Array сам может содержать одну и ту же букву дважды или даже больше, и их следует использовать так часто, как они происходят.

В дальнейшем Set должен содержать все комбинации от минимум 2 букв до длины данного Array.

Я искал здесь в 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"]" 

I знаете, это так ужасно неправильно во многих отношениях, но я застрял в этом коде и не знаю, h ow добавить рекурсивную функциональность.

Answer 1

Попробуйте это.

Общий алгоритм должен содержать fromList, содержащий буквы, которые вы еще не использовали, и номер toList, который является строкой, которую вы создали до сих пор. Это использует рекурсию для создания всех возможных строк и добавляет их к набору, когда длина 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 отметил в своем посте , решение выше немного медленное из-за всего создания и копирования наборов. Я изначально написал это, используя переменную inout для набора, но изменил ее на более функциональный интерфейс, чтобы было приятно звонить.

Вот моя оригинальная (быстрая) реализация, плюс я встроил ее в permute, который занимает всего [String] и возвращает Set<String>. Это делает работу по созданию в set и 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"} 

Edit: Я добавил параметр 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"] 

Answer 2

Это очень похоже на @ vacawama отвечают, но, надеюсь, отличается достаточно того, что он заслуживает отдельного ответа :)

Здесь массив с все комбинации построены (объяснение комментариев в строке):

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

Затем вы можете отфильтровать строки по крайней мере, две буквы, и преобразовать её в 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)) 

результат зависит от размера входного массива, обновленный метод но @ vacawama является самым быстрым:

 
# 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

В выходном примере не было ясно, что вы действительно хотите, либо:

1. все комбинации и перестановки из них:

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

2. только все комбинации:

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

Я могу порекомендовать большую библиотеку Swift @ oisdk: SwiftSequence для них, у нее много полезных функций. В разделе «Комбинации» он даже показывает пример его использования с Power Set, что почти точно то, что вы ищете в случае 1. При импорте файлов его библиотеки вы можете создать функцию powerSet на CollectionType s следующим образом:

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

Этот метод оценивается лениво, что означает, что он оценивается только тогда, когда ему это действительно нужно. Теперь вы упомянули, что хотите только иметь комбинации по меньшей мере из двух элементов. Это легко сделать с помощью метода 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) 

Но я настоятельно рекомендую использовать ленивый версия;) И да, чтобы удалить дубликаты, вы можете просто использовать Set(["A", "B", "C", "D"]) вместо просто ["A", "B", "C", "D"]

вы также можете сделать случай 2. на одном дыхании, как это:

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

Вот функция Swift 3, которая немного быстрее. Он основан на расширении типа Array, который может использоваться на массивах с любым типом элемента.

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

В моих тестах он работал примерно в 40 раз быстрее, чем вторая версия vacawama на 7 букв.

[EDIT] Я понял позже, что эта функция производит комбинации (по запросу в OP), где функция vacawama производит перестановки. Я протестировал эквивалентный алгоритм перестановок, и это было всего на 55% быстрее, чем у 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 
    } 
}