我正在嘗試學習遞歸并瀏覽斯坦福在線視頻講座和教科書。在編程練習中提出了一個問題，即為給定索引的字符串生成所有排列。例如"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"？
1 回答
青春有我
TA貢獻1784條經驗 獲得超8個贊
您走在正確的軌道上，整體形式看起來不錯，但細節仍然模糊。
首先，
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 個字符，我會感到困惑。
返回結果比產生打印等副作用更好，但出于教學目的，我將把它放在一邊。
這是一種解決方案（劇透警告?。?/p>
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
- 1 回答
- 0 關注
- 163 瀏覽
添加回答
舉報
0/150
提交
取消