允许相同字符串的快速字符串排列
允许相同字符串的快速字符串排列
提问于 2018-02-25 16:57:48
我见过其他关于字符串排列的问题，但它们并没有完全解决我的问题。
假设我有一个字符串数组：["A", "B", "C", "D", "E"]和我正在寻找一种方法来获得所有可能的组合，例如三个元素：
AAA，AAB，AAC，AAD，AAE，ABA，ACA，
其他排列的解决方案(例如here或here)不允许重复相同的元素，结果是：
ABC，ABD，ABE，BAC，
现在我使用了一种蛮力方法，可以进行多次迭代，但这当然是非常慢的(因为单个字符串的数量可能超过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
}可以想象，当需要添加更多的元素时，这种情况就会失控。
Stack Overflow用户
回答已采纳
发布于 2018-02-27 02:16:42
在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。
注意，我确信有更优雅的方法来实现上述目标，但希望这说明了基本的想法。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/48976065
复制相关文章
相似问题
腾讯云开发者
