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

问题描述

我目前正在尝试从 Strings 的 Array 中创建所有可能组合的 Set，每个元素只包含一个字母.

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

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

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

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

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

我在 stackoverflow 上搜索过这里，但只找到了忽略这样一个事实的置换函数，即每个字母应该只在它们出现的时候使用.

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.

这是我的第一个 Swift 2 项目，所以请原谅我的新手:)

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

我知道，这在很多方面都是非常错误的，但我被这段代码困住了，不知道如何添加递归功能.

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.

这是我的原始(更快)实现，另外我将它嵌入到一个 permute 中，它只需要一个 [String] 并返回一个 Set;.它完成创建set 和toList 数组的工作，然后调用permute 的内部版本来做真正的工作:

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.

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

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