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

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.

Setshould稍后包含从最少两个字母到给定数组长度的所有组合。

I searched here on *, 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 :)

这是我的第一个Swift 2项目，请原谅我的幼稚。

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.

我知道，这在很多方面都是大错特错的，但我还是坚持使用这段代码，不知道如何添加递归功能。

4 个解决方案

#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:

一般的算法是有一个包含尚未使用的字母的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"}

---

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.

正如@MartinR在他的文章中指出的，由于集合的创建和复制，上面的解决方案有点慢。我最初是使用inout变量为set编写的，但是为了更好地调用它，我将它改为功能更强的接口。

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:

这是我最初的(更快的)实现，加上我将它嵌入到一个permute中，该permute只接受一个[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: I added a minStringLen parameter (with default value of 2) instead of hard coding that value.

编辑:我添加了一个minStringLen参数(默认值为2)，而不是硬编码那个值。

See @MartinR's answer for performance comparisons.

参见@MartinR的性能比较答案。

---

Swift 3 and Swift 4:

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

#2

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

这与@vacawama的回答非常相似，但希望它足够不同，值得单独回答:

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):

我做了一个简单的性能比较(在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:

结果取决于输入数组的大小，但是@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

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

这是一个更快的3个函数。它基于数组类型的扩展，可以在任何元素类型的数组中使用。

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.

在我的测试中，它比vacawama的第二个版本快了40倍。

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

[编辑]我后来意识到这个函数产生组合(按照OP中的要求)，vacawama的函数产生排列。我测试了一个等效的排列算法，它比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
   }
}

#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:

我可以推荐@oisdk的伟大的Swift库:SwiftSequence for both them，它有很多有用的功能。在“组合”一节中，他甚至展示了它在电源集中的用法示例，这几乎正是您在case 1中所寻找的。导入他的库文件后，您可以在集合类型上创建powerSet函数，如下所示:

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:

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

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

但我强烈建议使用惰性版本;)是的，要删除重复，你可以使用Set([A]， B"， "C"， "D")而不是仅仅使用[A"， "B"， "C"， "D"]

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

你也可以做案例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("") })