我目前正在尝试从 Strings
的 Array
中创建所有可能组合的 Set
,每个元素只包含一个字母.
数组
本身可以包含相同的字母两次或更多次,并且它们只应在出现时使用。
Set
稍后应该包含从最少 2 个字母到给定 Array
长度的所有组合。
我在 stackoverflow 上进行了搜索,但只找到了忽略事实的排列函数,即每个字母只应在它们出现时使用。
这是我的第一个 Swift 2 项目,所以请原谅我的新手 :)
我想要什么
var array = ["A", "B", "C","D"]
var combinations: Set<String>
... <MAGIC> ...
print(combinations)
// "AB", "ABC", "ABD", "ABCD", "ABDC", "AC", "ACB", "ACD", "ACBD", "ACDB", and so on ...
我目前的做法
func permuation(arr: Array<String>) {
for (index, elementA) in arr.enumerate() {
//1..2..3..4
var tmpString = elementA
var tmpArray = arr
tmpArray.removeAtIndex(index)
for (index2, elementB) in tmpArray.enumerate() {
// 12..13..14
var tmpString2 = tmpString + elementB
var tmpArray2 = tmpArray
//[3,4]
tmpArray2.removeAtIndex(index2)
results.append(tmpString2)
}
}
}
permuation(array)
print(results)
// "["AB", "AC", "AD", "BA", "BC", "BD", "CA", "CB", "CD", "DA", "DB", "DC"]"
我知道,这在很多方面都是非常错误的,但我受困于这段代码,不知道如何添加递归功能。
最佳答案
试试这个。
一般的算法是有一个fromList
包含您尚未使用的字母和一个 toList
这是你到目前为止建立的字符串。这使用递归来构建所有可能的字符串,并在长度为 2 或更大时将它们添加到集合中:
func permute(fromList: [String], toList: [String] = [String](), var set: Set<String> = Set<String>()) -> Set<String> {
if toList.count >= 2 {
set.insert(toList.joinWithSeparator(""))
}
if !fromList.isEmpty {
for (index, item) in fromList.enumerate() {
var newFrom = fromList
newFrom.removeAtIndex(index)
set = permute(newFrom, toList: toList + [item], set: set)
}
}
return set
}
permute(["A", "B", "C"])
// {"BA", "AC", "ABC", "AB", "BCA", "CB", "BC", "CAB", "ACB", "CA", "CBA", "BAC"}
permute(["A", "A", "B"])
// {"BA", "BAA", "AAB", "AB", "ABA", "AA"}
更快的回答:
正如@MartinR 在他的帖子中指出的那样,由于所有的集合创建和复制,上面的解决方案有点慢。我最初是用 inout
写的set 的变量,但将其更改为功能更强大的接口(interface),以便更好地调用。
这是我最初的(更快的)实现,另外我将它嵌入了一个 permute
中只需要一个 [String]
并返回 Set<String>
.它负责创建 set
和 toList
数组然后调用 permute
的内部版本做真正的工作:
func permute(list: [String], minStringLen: Int = 2) -> Set<String> {
func permute(fromList: [String], toList: [String], minStringLen: Int, inout set: Set<String>) {
if toList.count >= minStringLen {
set.insert(toList.joinWithSeparator(""))
}
if !fromList.isEmpty {
for (index, item) in fromList.enumerate() {
var newFrom = fromList
newFrom.removeAtIndex(index)
permute(newFrom, toList: toList + [item], minStringLen: minStringLen, set: &set)
}
}
}
var set = Set<String>()
permute(list, toList:[], minStringLen: minStringLen, set: &set)
return set
}
permute(["A", "B", "C"])
// {"BA", "AC", "ABC", "AB", "BCA", "CB", "BC", "CAB", "ACB", "CA", "CBA", "BAC"}
permute(["A", "A", "B"])
// {"BA", "BAA", "AAB", "AB", "ABA", "AA"}
permute(["A", "A", "B"], minStringLen: 1)
// {"BA", "A", "BAA", "AB", "AA", "B", "AAB", "ABA"}
permute(["A", "A", "B"], minStringLen: 3)
// {"ABA", "BAA", "AAB"}
编辑:
我添加了一个 minStringLen
参数(默认值为 2
)而不是对该值进行硬编码。
有关性能比较,请参阅@MartinR 的回答。
Swift 3 和 Swift 4:
func permute(list: [String], minStringLen: Int = 2) -> Set<String> {
func permute(fromList: [String], toList: [String], minStringLen: Int, set: inout Set<String>) {
if toList.count >= minStringLen {
set.insert(toList.joined(separator: ""))
}
if !fromList.isEmpty {
for (index, item) in fromList.enumerated() {
var newFrom = fromList
newFrom.remove(at: index)
permute(fromList: newFrom, toList: toList + [item], minStringLen: minStringLen, set: &set)
}
}
}
var set = Set<String>()
permute(fromList: list, toList:[], minStringLen: minStringLen, set: &set)
return set
}
print(permute(list: ["A", "B", "C"]))
// ["ABC", "CA", "BAC", "ACB", "BA", "CAB", "BC", "CB", "BCA", "CBA", "AB", "AC"]
print(permute(list: ["A", "A", "B"]))
// ["AA", "AAB", "ABA", "AB", "BA", "BAA"]
print(permute(list: ["A", "A", "B"], minStringLen: 1))
// ["AAB", "ABA", "B", "BA", "A", "BAA", "AA", "AB"]
print(permute(list: ["A", "A", "B"], minStringLen: 3))
// ["AAB", "ABA", "BAA"]
关于ios - 如何生成所有可能的组合?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33021064/