在给定索引的情况下打印字符串的排列

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"，然后我的基本情况应该被触发并打印字符串。控件然后会回到应该是3和我选择"AB"的，但是我怎么选择呢？"i""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