問題內(nèi)容
我想編寫一個函數(shù)，將給定的處理程序應(yīng)用于所有輸入排列，而不返回整個排列。
代碼
（在 go 中）
查找排列：
// apply given handler on each combination, and return count only,
func findallpermutationapplyhandler[t any](ts []t, handler func([]t)) int {
n := 0
comblist := [][]t{{}} // when empty input, has 1 empty combination, not 0 combination,
for i := len(ts) - 1; i >= 0; i-- {
islastlevel := false
if i == 0 {
islastlevel = true
}
// prefix := ts[0:i]
mover := ts[i]
// fmt.printf("\nprefix = %v, mover = %v:\n", prefix, mover)
var comblist2 [][]t // combinations with an extra item added,
for _, comb := range comblist {
for j := 0; j <= len(comb); j++ { // insert mover at index j of comb,
comb2 := append(append(append([]t{}, comb[0:j]...), mover), comb[j:]...) // new_empty + left + mover + right
if islastlevel {
n++
handler(comb2)
} else {
comblist2 = append(comblist2, comb2)
}
}
}
comblist = comblist2
}
return n
}
登錄后復(fù)制
測試用例（簡單）：
func TestFindAllPermutationApplyHandler(t *testing.T) {
assert.Equal(t, FindAllPermutationApplyHandler([]int{1, 2, 3}, func(comb []int) {
fmt.Printf("\t%v\n", comb)
}), 6)
}
登錄后復(fù)制
說明
上面的函數(shù) findallpermutationapplyhandler() 可以查找排列，并將給定的處理程序應(yīng)用于每個組合。
但是它需要緩存之前的 n-1 級別（同時最近的 2 個級別）。
我已經(jīng)避免了最終級別的緩存，因為沒有更多級別依賴于它。
問題
-
是否可以避免緩存最近2個級別？
（又名，使空間復(fù)雜度為 o(1) 或 o(n)，甚至我猜 o(n^2) 更好）。。
-
但這對我來說似乎不可能，因為級別
i 是基于級別 i-1 的，對吧？
-
如果是的話，是否有更好的算法來降低空間復(fù)雜度？迭代是首選（而不是遞歸）。
正確答案
聽起來您正在尋找Pandita 算法
這是一種按字典順序迭代生成數(shù)組所有排列的簡單方法。
但是，它要求您可以對數(shù)組的元素進(jìn)行排序。如果不能（因為它們是泛型類型），那么您可以創(chuàng)建所有數(shù)組索引的輔助數(shù)組，并生成其排列。
