打印给定索引的字符串的排列

Question

我正在尝试学习递归并浏览斯坦福在线视频讲座和教科书。在编程练习中提出了一个问题，即为给定索引的字符串生成所有排列。例如"ABCD"和 索引 2。这应该生成"ABCD"和"ABDC"。

我了解如何通过使用生成排列，func permute(prefix, suffix)但这个问题让我感到困惑。这是我到目前为止想要的：

func permute(s string) {

    permuteHelper(s, 2)

}

func permuteHelper(s string, idx int) {

    if idx == 0 {

        fmt.Println(s)

        return

    }

    for i := idx; i < len(s); i++ {

        newS := s[:idx]

        suffix := s[idx : idx+1]

        newS += suffix

        permuteHelper(newS, idx-1)

    }

}

输出：

AB

AB

AB

AB

我不想要答案，但也许对我的思维过程有一些指导。我知道我应该创建一个静态"AB"，然后"C"在一次迭代中选择，然后选择"D"，然后我的基本情况应该被触发并打印字符串。然后控制会返回到"AB"，"i"应该是3，我选择"D"，但是我该如何选择呢"C"？

Answer 1

您走在正确的轨道上，整体形式看起来不错，但细节仍然模糊。首先，newS := s[:idx] suffix := s[idx : idx+1] newS += suffix相当于newS := s[:idx+1]这里并没有发生真正的排列；这是砍掉字符串的后面并i完全忽略循环变量。尝试为每个递归调用交换字符串中的两个字符，并使用两者i来idx执行此操作；可以将其视为与每个调用框架idx交换每个元素的固定枢轴i...len(s)。不过，确保您不会重新分配给当前作用域中的字符串，这很好，因为这会扰乱循环后续迭代的状态。第二个建议：为了建立基本情况，递归地向上计数len(s)而不是向下计数到零。您几乎可以假装数组的整个第一个块不存在。可以将其视为常规排列算法，只不过您跳过了第一个idx索引。另外，这更多的是一个设计点，而不是一个算法问题，但我会将参数公开idx给调用者，而不是将其隐藏在包装器后面。permute这使得该函数可重用，并且其作用更加明显 - 作为库的用户，如果名为的函数拒绝排列前 2 个字符，我会感到困惑。返回结果比产生打印等副作用更好，但出于教学目的，我将把它放在一边。这是一种解决方案（剧透警告！）：package main import "fmt" func permute(s string, idx int) {    if idx == len(s) {        fmt.Println(s)    }     for i := idx; i < len(s); i++ {        a := []rune(s)        a[i], a[idx] = a[idx], a[i]        permute(string(a), idx + 1)    }} func main() {    permute("abcde", 2)}permute("abcde", 2)产生abcde abced abdce abdec abedc abecd