如何产生所有可能的组合？ [英] How to generate all possible combinations?

问题描述

我目前正在试图从<$ C $的阵列进行所有可能的组合的设置 C>字符串，是每一个元素只包含一个字母。

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.

的设置稍后应该包含至少2个英文字母都组合到的长度定阵列

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.

这是我第一次斯威夫特2项目，所以请原谅我的greenhornish岬：）

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

我要什么

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

我知道，这是所以在很多方面极其错误的，但我仍坚持这一code，不知道如何添加一个递归功能。

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.

推荐答案

试试这个。

一般的算法是有一个 fromlist里包含字母，你还没有使用和了ToList 的是目前为止你已经建立起来的字符串。这种使用递归构建了所有可能的字符串，并将其添加到集时长为2或更大：

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

---

更快的答案：

由于@MartinR在他的文章中指出，上述解决方案，是因为所有的集创作和复制的有点慢。我原本写了这个使用集的 INOUT 变量，但它改成了更多的功能接口，使其很好的调用。

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.

下面是我原来的（快）的实施，再加上我嵌在一个置换即只需一个 [字符串] 并返回设置＆LT;串GT; 。它创建设置和了ToList 数组，然后调用的内部版本置换做真正的工作：

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

编辑：
我添加了一个 minStringLen 参数（与 2 默认值），而不是硬编码该值。

I added a minStringLen parameter (with default value of 2) instead of hard coding that value.

请参阅@ MartinR的回答对性能比较。

See @MartinR's answer for performance comparisons.

这篇关于如何产生所有可能的组合？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！