swift - 快速剖析排列算法

Question

我正在寻找一种字符串排列算法，我找到了这个。

    import Foundation

    func permuteHelper(_ str:String, _ chosen:String){
        var chosen = chosen
        var str = str
        if str.count == 0 {
            print(chosen)
        } else {
            for index in str.indices {
                //choose
                let charac = str[index]
                chosen.append(charac)
                str.remove(at: index)
                // explore
                print("call recursion")
                permuteHelper(str, chosen)
                print("return from recursion")
                //unchoose
                str.insert(charac, at: index)
                chosen.removeLast()
            }
        }
    }

    func permute(_ str:String){
        permuteHelper(str, "")
    }

    var str = "ABC"
    permute(str)

我运行它，然后它打印执行结果:

call recursion
call recursion
call recursion
ABC
return from recursion
return from recursion
call recursion
call recursion
ACB
return from recursion
return from recursion
return from recursion
call recursion
call recursion
call recursion
BAC
return from recursion
return from recursion
call recursion
call recursion
BCA
return from recursion
return from recursion
return from recursion
call recursion
call recursion
call recursion
CAB
return from recursion
return from recursion
call recursion
call recursion
CBA
return from recursion
return from recursion
return from recursion
Program ended with exit code: 0

在前 8 行中，它具有第一个循环，结果为:ABC。对我来说，它看起来很奇怪，它使 3 调用递归，显示结果，然后完成 2 从递归返回并开始新的循环。

我的问题是:

在开始新的循环之前，不应该返回到第三从递归返回吗？

==>>更新

按照 Martin R 的建议，在 permuteHelper 中添加 level 参数后 func permuteHelper(_ str:String, _ selected:String, _ level:Int) 。看起来该算法在打印两个排列后完成了一个循环。如下:

call recursion Level: 1
call recursion Level: 2
call recursion Level: 3
ABC
return from recursion Level: 3
return from recursion Level: 2
call recursion Level: 2
call recursion Level: 3
ACB
return from recursion Level: 3
return from recursion Level: 2
return from recursion Level: 1
call recursion Level: 1
call recursion Level: 2
call recursion Level: 3
BAC
return from recursion Level: 3
return from recursion Level: 2
call recursion Level: 2
call recursion Level: 3
BCA
return from recursion Level: 3
return from recursion Level: 2
return from recursion Level: 1
call recursion Level: 1
call recursion Level: 2
call recursion Level: 3
CAB
return from recursion Level: 3
return from recursion Level: 2
call recursion Level: 2
call recursion Level: 3
CBA
return from recursion Level: 3
return from recursion Level: 2
return from recursion Level: 1
Program ended with exit code: 0

Answer 1

It is not suppose to came back to third return from recursion before starts a new cycle?

没有。开头的两次返回和两次调用是在算法为字符串 BC 生成排列时发生的(在顶层选择了 A)。

需要进行三次递归才能为 ABC 的每个排列选择第一个字母。要选择第二个字母，需要对原始字符串的两个字符减去第一个选择的字符进行两次递归。要选取第三个字母，需要一次递归，因为只有一个字符串可供选取。

不幸的是，由于您正在循环中执行某些工作并且“调用递归”诊断处于循环中，因此情况变得更加困惑。因此，当 string 长度超过一个字符时，您会在同一级别获得多个诊断信息。