计算Swift中字符串的所有排列 [英] Calculate all permutations of a string in Swift

问题描述

对于字符串"ABC"，下面的代码段计算了6个总置换中的5个.我的策略是在每个索引可能的索引处插入每个字符.但是函数永远不会将"CBA"作为可能的排列.我想念什么?

For the string "ABC" the code snippet below calculates 5 of the 6 total permutations. My strategy was to insert each character at each index possible index. But the function never gets "CBA" as a possible permutation. What am I missing?

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很好地说明了使用Heap的算法，但是我认为您有一个重要的问题，为什么您的代码不起作用"不能正常工作，以及如何调试它.

While Stefan and Matt make a good point about using Heap's algorithm, I think you have an important question about why your code doesn't work and how you would debug that.

在这种情况下，该算法根本是不正确的，并且发现这种现象的最佳方法是使用纸和笔IMO.您要做的是拾取每个元素，将其从数组中删除，然后将其注入每个可能的位置.您的代码可以执行您要求的操作.但是以这种方式进入"CBA"是不可能的.您一次只移动一个元素，但是"CBA"有两个 元素乱序.如果您扩展到ABCD，则会发现更多缺少的排列(仅生成24个排列中的10个).

In this case, the algorithm is simply incorrect, and the best way to discover that is with pencil and paper IMO. What you are doing is picking each element, removing it from the array, and then injecting it into each possible location. Your code does what you have asked it to do. But it's not possible to get to "CBA" that way. You're only moving one element at a time, but "CBA" has two elements out of order. If you expanded to ABCD, you'd find many more missing permutations (it only generates 10 of the 24).

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

While Heap's algorithm is nicely efficient, the deeper point is that it walks through the entire array and swaps every possible pair, rather than just moving a single element through the array. Any algorithm you choose must have that property.

为了让我大吃一惊，我将以这种方式扩展Matt的实现:

And just to throw my hat into the ring, I'd expand on Matt's implementation this way:

// 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中字符串的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！