algorithm - 使用递归的字符串排列

Question

例如，如果我有一个字符串 {a, b, c}。我需要在控制台上打印出所有排列而不重复从 1 个字母到 3 个字母的字母，如下所示:

a b c ab ac abc acb ba bc bac bca ca cb cab cba

我如何使用递归来写这个？

Answer 1

如果您需要将所有字符排列成一个字符串，您可以使用递归函数。

这是 Swift 中的代码。

func visit(unused:[Character], used: [Character] = [Character]()) -> [String] {
    var result = [String(used)]
    for (index, char) in unused.enumerate() {
        var unused = unused
        unused.removeAtIndex(index)
        var used = used
        used.append(char)
        result = result + visit(unused, used: used)
    }
    return result
}

如您所见，该函数接收 2 个参数:

• unused:表示尚未使用的字符列表
• used:用于构建输出的可能元素的字符。此参数是可选的，因此如果未将其传递给函数，则会使用一个空数组(这对第一次调用很有用)。

测试

let word = "abc"
let chars = [Character](word.characters)
print(visit(chars))

["", "a", "ab", "abc", "ac", "acb", "b", "ba", "bac", "bc", "bca", "c", "ca", "cab", "cb", "cba"]

省略空字符串

此结果也包含空字符串，但您可以轻松忽略此值，只需更新函数，如下所示。

func visit(unused:[Character], used: [Character] = [Character]()) -> [String] {
    var result = [String]()
    if !used.isEmpty {
        result.append(String(used))
    }
    for (index, char) in unused.enumerate() {
        var unused = unused
        unused.removeAtIndex(index)
        var used = used
        used.append(char)
        result = result + visit(unused, used: used)
    }
    return result
}