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

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)    }}输出：ABABABAB我不想要答案，但也许对我的思维过程有一些指导。我知道我应该创建一个静态"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