列出字符串数组中所有元组的算法 [英] Algorithm to list all tuples from an array of String

问题描述

我正在尝试解决以下问题，给定大小为n的String数组，列出该数组中的所有n个元组，即：

I'm trying to solve the following problem, given an array of String, of size n, list all n-tuples from this array, that is:

let A: [String] = ["a","b","c",...]

确定所有元组

[ abc ..， bac ..， ...] ，其中恰好有n！。

我已经在Swift中编写了一个解决方案，但我不太清楚它对结果感到满意，因为它使用了闭包，从而难以遍历元组。

I've written a solution in Swift, but I'm not quite happy with the result, as it uses closures, making it difficult to iterate over the tuples.

这里是代码，以防万一：

Here's the code, just in case:

public func tuple(seq:[String], value:String, block:(String) -> ()) {
    if seq.count > 0 {
        for i in 0..<seq.count {
            var uu = seq;
            let kk:String = uu[i];
            uu.remove(at: i)
            self.tuple(seq:uu,value: value + kk, block: block)
        }
    } else {
        block(value)
    }
}

具有有效解决方案但没有关闭的任何人？

Anyone with a valid solution without closure?

推荐答案

使用在Code Review上按字典顺序对排列进行基于顺序的枚举（已针对
Swift 4更新，并已实施Hamish答案的建议）：

Using the code from Sequence-based enumeration of permutations in lexicographic order on Code Review (updated for Swift 4, and with the suggestions from Hamish's answer implemented):

extension Array where Element: Comparable {

    /// Replaces the array by the next permutation of its elements in lexicographic
    /// order.
    ///
    /// It uses the "Algorithm L (Lexicographic permutation generation)" from
    ///    Donald E. Knuth, "GENERATING ALL PERMUTATIONS"
    ///    http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz
    ///
    /// - Returns: `true` if there was a next permutation, and `false` otherwise
    ///   (i.e. if the array elements were in descending order).

    mutating func permute() -> Bool {

        // Nothing to do for empty or single-element arrays:
        if count <= 1 {
            return false
        }

        // L2: Find last j such that self[j] < self[j+1]. Terminate if no such j
        // exists.
        var j = count - 2
        while j >= 0 && self[j] >= self[j+1] {
            j -= 1
        }
        if j == -1 {
            return false
        }

        // L3: Find last l such that self[j] < self[l], then exchange elements j and l:
        var l = count - 1
        while self[j] >= self[l] {
            l -= 1
        }
        self.swapAt(j, l)

        // L4: Reverse elements j+1 ... count-1:
        var lo = j + 1
        var hi = count - 1
        while lo < hi {
            self.swapAt(lo, hi)
            lo += 1
            hi -= 1
        }
        return true
    }
}

struct PermutationSequence<Element : Comparable> : Sequence, IteratorProtocol {

    private var current: [Element]
    private var firstIteration = true

    init(startingFrom elements: [Element]) {
        self.current = elements
    }

    init<S : Sequence>(_ elements: S) where S.Iterator.Element == Element {
        self.current = elements.sorted()
    }

    mutating func next() -> [Element]? {

        var continueIterating = true

        // if it's the first iteration, we avoid doing the permute() and reset the flag.
        if firstIteration {
            firstIteration = false
        } else {
            continueIterating = current.permute()
        }

        // if the array changed (and it isn't the first iteration), then return it,
        // else we're at the end of the sequence.
        return continueIterating ? current : nil
    }
}

一个人可以非常有效地迭代所有排列数组：

one can very efficiently iterate over all permutations of an array:

let a = ["a", "b", "c"]
let permSeq = PermutationSequence(startingFrom: a)

for tuple in permSeq {
    print(tuple.joined())
}

每次调用迭代器都会创建下一个排列，并且仅需要
固定数量的额外存储空间（当前
的一个数组）排列和一个布尔变量）。

Each call to the iterator creates the next permutation, and only a fixed amount of additional storage is needed (one array for the current permutation, and a boolean variable).

这篇关于列出字符串数组中所有元组的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！