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

一尘不染

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

swift

目前，我试图让Set所有可能的组合从Array的Strings，是每一个元素只包含一个字母。

在Array本身包含相同字母两次甚至更多，他们只应该，因为他们经常会出现使用。

在Set稍后应该含有最多的给定的长度从最小的2个字母的所有组合Array。

我在此处搜索了stackoverflow，但只发现了忽略以下事实的置换函数：每个字母仅在出现时才经常使用。

这是我的第一个Swift 2项目，所以请原谅我的绿色态度:)

我想要的是

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

我知道，在很多方面这都是非常糟糕的错误，但是我仍然坚持使用此代码，并且不知道如何添加递归功能。

阅读 265

2020-07-07

共1个答案

一尘不染

试试这个。

通用算法是让一个fromList包含尚未使用的字母，而a
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在他的帖子中指出的那样，由于所有集的创建和复制，上述解决方案有点慢。我最初是使用inoutset变量编写此函数的，但后来将其更改为功能更强的接口，以使其易于调用。

这是我最初的（更快的）实现，再加上我将其嵌入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"}

编辑： 我添加了一个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"]

2020-07-07