允许相同字符串的快速字符串排列
我见过其他关于字符串排列的问题，但它们并没有完全解决我的问题。
假设我有一个字符串数组：["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
}可以想象，当需要添加更多的元素时，这种情况就会失控。
回答 2
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用户
发布于 2018-02-25 18:40:19
将您的排列视为自定义位置数字系统中的序列号。
"AAA，AAB，AAC，AAD，AAE，ABA，ACA，……“
正如您的示例所示，您基本上希望用替换的方法更改唯一的单字母字符串；使用固定的样本大小(上面；3)。如果是这样的话，您可以将您的字母视为自定义数字位置数字系统中的唯一数字，特别是一个基5系统，您希望对该系统计算最多以3位数表示的所有数字。最后，如果您使用的数字比允许的要少(A)，则需要使用前导“零”(<3)填充所有数字。
考虑到这一特殊情况，我们可以很容易地使用String(_:radix:)和Int(_:radix:)初始化器将基10数字转换为特定的数字系统，并实现如下非递归方法：
// Helper to pad the presented numbers to a given width.
extension String {
func leftPadded(with padding: Character, toAtLeast width: Int) -> String {
return count >= width ? self
: String(repeating: padding, count: width - count) + self
}
}
let digits = ["A", "B", "C", "D", "E"]
let base = digits.count
let width = 3
if let zero = digits.first.map(Character.init) {
// Iterate and convert to your numeral system.
for i in 0..<((0..<width).reduce(1) { (p, _) in p * base }) {
let nonPaddedPermutation = String(i, radix: base)
.flatMap { Int(String($0), radix: base) }
.map { String(digits[$0]) }
.joined()
print(nonPaddedPermutation.leftPadded(with: zero, toAtLeast: width))
} /* AAA
AAB
...
EED
EEE */
}或者，更一般的(将允许的数字视为字符而不是单字符字符串)：
extension String {
func leftPadded(with padding: Character, toAtLeast width: Int) -> String {
return count >= width ? self
: String(repeating: padding, count: width - count) + self
}
}
extension Array where Element == Character {
// Limitation: all elements are unique (otherwise: `nil` return)
func replacementPermute(sampleSize width: Int) -> [String]? {
guard count == Set(self).count else { return nil }
var permutations: [String] = []
if let zero = first {
let numPerms = ((0..<width).reduce(1) { (p, _) in p * count })
permutations.reserveCapacity(numPerms)
for i in 0..<numPerms {
let nonPaddedPermutation = String(i, radix: count)
.flatMap { Int(String($0), radix: count) }
.map { String(self[$0]) }
.joined()
permutations.append(nonPaddedPermutation
.leftPadded(with: zero, toAtLeast: width))
}
}
return permutations
}
}
// Example usage:
if let permutations = ["A", "", "C", "D", "E"]
.flatMap(Character.init).replacementPermute(sampleSize: 3) {
print(permutations)
// ["AAA", "AA", "AAC", ... "EEA", "EE", "EEC", "EED", "EEE"]
}https://stackoverflow.com/questions/48976065
复制相似问题
腾讯云开发者
