计算一个string在Swift中的所有排列
对于string"ABC" ，下面的代码片段计算6个总排列中的5个。 我的策略是在每个索引可能的索引处插入每个字符。 但是这个函数从来没有得到"CBA"作为一个可能的排列。 我错过了什么？
var permutationArray:[String] = []; let string: String = "ABC" func permute(input: String) -> Array<String> { var permutations: Array<String> = [] /* Convert the input string into characters */ var inputArray: Array<String> inputArray = input.characters.map { String($0) } print(inputArray) /* For each character in the input string... */ for var i = 0; i < inputArray.count; i++ { /* Insert it at every index */ let characterInArray: String = inputArray[i] var inputArrayCopy: Array<String> = [] for var y = 0; y < inputArray.count; y++ { inputArrayCopy = inputArray inputArrayCopy.removeAtIndex(i) inputArrayCopy.insert(characterInArray, atIndex:y) let joiner = "" let permutation = inputArrayCopy.joinWithSeparator(joiner) if !permutations.contains(permutation) { permutations.insert(permutation, atIndex: 0) } } } return permutations } var permutations = permute(string) print(permutations)
虽然Stefan和Matt在使用堆的algorithm方面做了很好的工作，但是我认为你有一个重要的问题，那就是为什么你的代码不工作以及如何debugging。
在这种情况下，algorithm是不正确的，发现的最好方法是用铅笔和纸张IMO。 你正在做的是挑选每个元素，将其从数组中删除，然后将其注入到每个可能的位置。 你的代码做你要求做的事情。 但是这样做到“CBA”是不可能的。 一次只能移动一个元素，但是“CBA”有两个元素无序。 如果你扩展到ABCD，你会发现更多的丢失排列（它只产生24个中的10个）。
虽然Heap的algorithm效率很高，但更深层次的一点是，它遍历整个数组并交换每一对可能的数组，而不是仅仅通过数组移动单个元素。 您select的任何algorithm必须具有该属性。
只要把我的帽子扔进戒指，我就可以通过这种方式来扩展Matt的实现：
// Takes any collection of T and returns an array of permutations func permute<C: Collection>(items: C) -> [[C.Iterator.Element]] { var scratch = Array(items) // This is a scratch space for Heap's algorithm var result: [[C.Iterator.Element]] = [] // This will accumulate our result // Heap's algorithm func heap(_ n: Int) { if n == 1 { result.append(scratch) return } for i in 0..<n-1 { heap(n-1) let j = (n%2 == 1) ? 0 : i scratch.swapAt(j, n-1) } heap(n-1) } // Let's get started heap(scratch.count) // And return the result we built up return result } // We could make an overload for permute() that handles strings if we wanted // But it's often good to be very explicit with strings, and make it clear // that we're permuting Characters rather than something else. let string = "ABCD" let perms = permute(string.characters) // Get the character permutations let permStrings = perms.map() { String($0) } // Turn them back into strings print(permStrings) // output if you like
下面是Swift中Heap（Sedgewick's？）algorithm的一个expression式。 这是有效的，因为数组是通过引用传递的，而不是通过值传递（当然这意味着你必须准备好让数组被篡改）。 通过使用内置的swapAt(_:_:)函数来高效地expression交换：
func permutations(_ n:Int, _ a: inout Array<Character>) { if n == 1 {print(a); return} for i in 0..<n-1 { permutations(n-1,&a) a.swapAt(n-1, (n%2 == 1) ? 0 : i) } permutations(n-1,&a) }
让我们试试看：
var arr = Array("ABC".characters) permutations(arr.count,&arr)
输出：
["A", "B", "C"] ["B", "A", "C"] ["C", "A", "B"] ["A", "C", "B"] ["B", "C", "A"] ["C", "B", "A"]
如果你想要做的每一个置换不仅仅是打印，用其他的东西来代替print(a) 。 例如，你可以将每个置换附加到一个数组，将字符数组组合成一个string。
func generate(n: Int, var a: [String]){ if n == 1 { print(a.joinWithSeparator("")) } else { for var i = 0; i < n - 1; i++ { generate(n - 1, a: a) if n % 2 == 0 { let temp = a[i] a[i] = a[n-1] a[n-1] = temp } else { let temp = a[0] a[0] = a[n-1] a[n-1] = temp } } generate(n - 1, a: a) } } func testExample() { var str = "123456" var strArray = str.characters.map { String($0) } generate(str.characters.count, a: strArray) }
不要重新发明轮子。 这是Heapalgorithm的一个简单的端口。
这是我的解决scheme。
import Foundation class Permutator { class func permutation(_ str: String) -> Set<String> { var set = Set<String>() permutation(str, prefix: "", set: &set) return set } private class func permutation(_ str: String, prefix: String, set: inout Set<String>) { if str.characters.count == 0 { set.insert(prefix) } for i in str.characters.indices { let left = str.substring(to: i) let right = str.substring(from: str.index(after: i)) let rem = left + right permutation(rem, prefix: prefix + String(str[i]), set: &set) } } } let startTime = Date() let permutation = Permutator.permutation("abcdefgh") print("\(permutation) \n") print("COMBINAISON: \(permutation.count)") print("TIME: \(String(format: "%.3f", Date().timeIntervalSince(startTime)))s")
您可以将其复制/粘贴到一个文件中并使用命令行swift二进制文件执行它。
对于所有唯一字符的排列，该algorithm需要大约0.06秒才能执行。