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

我正在尝试学习递归并浏览斯坦福在线视频讲座和教科书。在编程练习中,提出了一个问题,以生成给定索引的字符串的所有排列。例如"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",然后我的基本情况应该被触发并打印字符串。控件然后会回到应该是3和我选择"AB"的,但是我怎么选择呢?"i""D""C"


ABOUTYOU
浏览 122回答 1
1回答

一只名叫tom的猫

你在正确的轨道上,整体形式看起来不错,但细节仍然模糊。首先,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&nbsp;import "fmt"&nbsp;func permute(s string, idx int) {&nbsp; &nbsp; if idx == len(s) {&nbsp; &nbsp; &nbsp; &nbsp; fmt.Println(s)&nbsp; &nbsp; }&nbsp;&nbsp; &nbsp; for i := idx; i < len(s); i++ {&nbsp; &nbsp; &nbsp; &nbsp; a := []rune(s)&nbsp; &nbsp; &nbsp; &nbsp; a[i], a[idx] = a[idx], a[i]&nbsp; &nbsp; &nbsp; &nbsp; permute(string(a), idx + 1)&nbsp; &nbsp; }}&nbsp;func main() {&nbsp; &nbsp; permute("abcde", 2)}permute("abcde", 2)生产abcdeabcedabdceabdecabedcabecd
打开App,查看更多内容
随时随地看视频慕课网APP

相关分类

Go