列出字符串数组中所有元组的算法 [英] 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屋!