快速的字符串排列允许相同的字符串 [英] swift string permutations allowing the same strings
问题描述
我还看到了有关字符串排列的其他问题，但是它们并没有完全覆盖我的问题.
假设我有一个字符串数组:["A", "B", "C", "D", "E"]，并且我正在寻找一种方法来获取例如三个元素的 all 个可能组合:
AAA，AAB，AAC，AAD，AAE，ABA，ACA，...
其他置换解决方案(例如，此处，或此处)不允许重复相同的元素，结果:
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
}
可以想象，当要添加更多元素时，这种情况将一发不可收拾.
在另一个问题中，您询问如何过滤dfri的答案(+1)的结果可修剪出元素顺序不同的重复项(例如，如果结果集包含"AAB"，"ABA"和"BAA"，则修剪后两个元素). /p>
如果这是您要执行的操作，建议您编写一个直接返回该解决方案集的函数:
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"]
这种方法将避免需要后来过滤结果.
请注意，我敢肯定有更多优雅的方法可以实现上述目的，但是希望这可以说明基本思想.
I have seen other questions about string permutations, but they don't completely cover my question.
Suppose I have an array of strings: ["A", "B", "C", "D", "E"] and I am looking for a way to get all possible combinations of for instance three elements:
AAA, AAB, AAC, AAD, AAE, ABA, ACA, ...
Other solutions for permutations (e.g. here, or here) don't allow the same element to be duplicated, and result in:
ABC, ABD, ABE, BAC, ...
I now use a brute-force approach, with many iterations, but of course that is super slow (because the number of individual strings can be more than 10)
Any ideas how to tackle this?
This is what I have now:
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
}
One can imagine this gets out of hand when more elements are to be added.
In another question, you ask how to filter the results from dfri's answer (+1) to prune out duplicates resulting from a different order of elements (e.g. if you got a result set with "AAB", "ABA", and "BAA", prune out the latter two).
If that's what you want to do, I'd suggest writing a function that just returned that set of solutions directly:
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)
}
}
}
Thus:
let array = ["A", "B", "C", "D"]
let result = array.combinations(size: 2, allowDuplicates: true)
would return:
["AA", "AB", "AC", "AD", "BB", "BC", "BD", "CC", "CD", "DD"]
And if you didn't want it to allow duplicates:
let result = array.combinations(size: 2)
would return:
["AB", "AC", "AD", "BC", "BD", "CD"]
This approach would avoid needing to later filter the results.
Note, I'm sure there are more elegant ways to achieve the above, but hopefully this illustrates the basic idea.
这篇关于快速的字符串排列允许相同的字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
