How to generate all possible combinations?

问题:

I'm currently trying to make a Set of all possible combinations from an Array of Strings, were each element contains only one letter.

The Array itself can contain the same letter twice or even more and they should only be used as often as they occur.

The Setshould later contain all combinations from a minimum of 2 letters up to the length of the given Array.

I searched here on stackoverflow, but only found permutation functions that ignore the fact, that each letter should only be used as often as they occur.

This is my first Swift 2 project, so please forgive my greenhornish-ness :)

What I want

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

My current approach

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 know, this is so terribly wrong in so many ways, but I'm stuck with this code, and don't know how to add a recursive functionality.

回答1:

Try this.

The general algorithm is to have a fromList containing the letters you haven't used yet and a toList that is the string you've built up so far. This uses recursion to build up all possible strings and adds them to the set when the length is 2 or greater:

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

---

Faster Answer:

As @MartinR pointed out in his post, the solution above is a little slow because of all of the creation and copying of sets. I had originally written this using an inout variable for set, but changed it to the more functional interface to make it nice to call.

Here is my original (faster) implementation, plus I embedded it in a permute that takes just an [String] and returns a Set<String>. It does the work of creating the set and the toList array and then calls the inner version of permute to do the real work:

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: I added a minStringLen parameter (with default value of 2) instead of hard coding that value.

See @MartinR's answer for performance comparisons.

---

Swift 3 and 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"]

回答2:

This is quite similar to @vacawama's answer, but hopefully different enough that it deserves a separate answer :)

Here, an array with all combinations is built (explaining comments inline):

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

Then you can filter the strings with at least two letters, and convert it to a 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"]

I made a simple performance comparison (compiled in Release mode on a 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))

The result depends on the size of the input array, but @vacawama's updated method is the fastest:

# 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

回答3:

Here's a Swift 3 function that is a bit faster. It is based on an extension to the Array type that can be used on arrays with any element type.

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

In my tests, it ran about 40x faster than vacawama's second version on 7 letters.

[EDIT] I realized later that this function produces combinations (as requested in the OP) where vacawama's function produces permutations. I tested an equivalent algorithm for permutations and it was merely 55% faster than vacawama's.

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

回答4:

In your output example it wasn't clear what you really want, either:

1. all combinations and permutations of them:

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

2. just all combinations:

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

I can recommend @oisdk's great Swift library: SwiftSequence for both of them, it has lots of useful functions. In the Combinations section he even shows an example of its usage with the Power Set, which is almost exactly what you're looking for in case 1. Upon importing the files of his library, you can create the powerSet function on CollectionTypes like this:

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

This method evaluates lazily, which means that it's only evaluated when it really needs to. Now you mentioned that you only want to have combinations of at least 2 elements. This is easily done with the filter method:

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

For case 2. where you need permutations of those as well, you can do this:

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

You can convert these to a Set of Strings or an Array:

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

But I strongly recommend to use the lazy version ;) And yes, to remove duplicates you can just use Set(["A", "B", "C", "D"]) instead of just ["A", "B", "C", "D"]

You can also do case 2. in one go like this:

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