ios - 在 Swift 中计算字符串的所有排列

Question

对于字符串 "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)

Answer 1

虽然 Stefan 和 Matt 就使用 Heap 的算法提出了一个很好的观点，但我认为您有一个重要的问题，即为什么您的代码不起作用以及您将如何调试它。

在这种情况下，该算法完全不正确，发现它的最佳方法是使用纸笔 IMO。您正在做的是挑选每个元素，将其从数组中删除，然后将其注入(inject)每个可能的位置。您的代码执行您要求它执行的操作。但不可能以这种方式进入“CBA”。您一次只移动一个元素，但“CBA”有 两个 元素乱序。如果您扩展到 ABCD，您会发现更多缺失的排列(它只生成 24 个排列中的 10 个)。

虽然 Heap 的算法非常高效，但更深层次的一点是它会遍历整个数组并交换每个可能的对，而不是仅仅在数组中移动单个元素。您选择的任何算法都必须具有该属性。

顺便说一下，我将以这种方式扩展 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