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

Question

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

它Array本身可以包含相同的字母两次甚至更多,它们应该只在它们出现时使用.

之后Set应该包含从最少2个字母到给定长度的所有组合Array.

我在这里搜索了stackoverflow,但只找到了忽略这个事实的排列函数,每个字母只应该在它们出现时经常使用.

这是我的第一个Swift 2项目,所以请原谅我的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"]"

我知道,这在很多方面都是非常错误的,但是我坚持使用这段代码,并且不知道如何添加递归功能.

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在他的帖子中指出的那样,由于所有的集合的创建和复制,上面的解决方案有点慢.我最初使用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"]

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