目前,我试图让Set所有可能的组合从Array的Strings,是每一个元素只包含一个字母。
Set
Array
Strings
在Array本身包含相同字母两次甚至更多,他们只应该,因为他们经常会出现使用。
在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包含尚未使用的字母,而a toList则是您到目前为止建立的字符串。这使用递归来构建所有可能的字符串,并在长度为2或更大时将它们添加到集合中:
fromList
toList
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在他的帖子中指出的那样,由于所有集的创建和复制,上述解决方案有点慢。我最初是使用inoutset变量编写此函数的,但后来将其更改为功能更强的接口,以使其易于调用。
inout
这是我最初的(更快的)实现,再加上我将其嵌入permute仅需输入[String]并返回的Set<String>。它完成创建set和toList数组的工作,然后调用的内部版本进行permute实际工作:
permute
[String]
Set<String>
set
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),而不是对该值进行硬编码。
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"]