允许相同字符串的快速字符串排列

Question

我看过其他关于字符串排列的问题，但它们并没有完全涵盖我的问题。

假设我有一个字符串数组:["A", "B", "C", "D", "E"] 我正在寻找一种方法来获取 例如三​​个元素的所有可能组合:

AAA, AAB, AAC, AAD, AAE, ABA, ACA, ...

排列的其他解决方案(例如 here 或 here )不允许重复相同的元素，并导致:

ABC, ABD, ABE, BAC, ...

我现在用的是蛮力法，有很多次迭代，当然那是 super 慢的(因为单个字符串的数量可能超过 10 个)

有什么解决办法吗？

这是我现在拥有的:

func getVariations() -> [String] {
var variations = [String]()

let elements = ["A", "B", "C", "D", "E"]

for e1 in elements {
    variations.append(e1)

    for e2 in elements {
        variations.append(e1 + e2)

        for e3 in elements {
            variations.append(e1 + e2 + e3)

            for e4 in elements {
                variations.append(e1 + e2 + e3 + e4)
            }
        }
    }

    return variations
}

可以想象，当要添加更多元素时，这会失控。

Answer 1

在another question ，您询问如何过滤 dfri 的答案 (+1) 的结果以删除因元素的不同顺序而产生的重复项(例如，如果您得到包含“AAB”、“ABA”和“BAA”的结果集，请删除后两者)。

如果那是你想要做的，我建议编写一个直接返回那组解决方案的函数:

extension Array where Element: StringProtocol {

    /// Return combinations of the elements of the array (ignoring the order of items in those combinations).
    ///
    /// - Parameters:
    ///   - size: The size of the combinations to be returned.
    ///   - allowDuplicates: Boolean indicating whether an item in the array can be repeated in the combinations (e.g. is the sampled item returned to the original set or not).
    ///
    /// - Returns: A collection of resulting combinations.

    func combinations(size: Int, allowDuplicates: Bool = false) -> [String] {
        let n = count

        if size > n && !allowDuplicates { return [] }

        var combinations: [String] = []

        var indices = [0]

        var i = 0

        while true {
            // build out array of indexes (if not complete)

            while indices.count < size {
                i = indices.last! + (allowDuplicates ? 0 : 1)
                if i < n {
                    indices.append(i)
                }
            }

            // add combination associated with this particular array of indices

            combinations.append(indices.map { self[$0] }.joined())

            // prepare next one (incrementing the last component and/or deleting as needed

            repeat {
                if indices.count == 0 { return combinations }
                i = indices.last! + 1
                indices.removeLast()
            } while i > n - (allowDuplicates ? 1 : (size - indices.count))
            indices.append(i)
        }
    }
}

因此:

let array = ["A", "B", "C", "D"]
let result = array.combinations(size: 2, allowDuplicates: true)

会返回:

["AA", "AB", "AC", "AD", "BB", "BC", "BD", "CC", "CD", "DD"]

如果您不希望它允许重复:

let result = array.combinations(size: 2)

会返回:

["AB", "AC", "AD", "BC", "BD", "CD"]

这种方法将避免需要 later filter the results .

请注意，我确信有更优雅的方法可以实现上述目标，但希望这能说明基本思想。