在排列上應用處理程序，而不需要級別快取？

問題內容

我想寫一個函數，將給定的處理程序套用到所有輸入排列，而不回傳整個排列。

程式碼

（在 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
  }

• 測試案例（簡單）：

  func TestFindAllPermutationApplyHandler(t *testing.T) {
      assert.Equal(t, FindAllPermutationApplyHandler([]int{1, 2, 3}, func(comb []int) {
          fmt.Printf("\t%v\n", comb)
      }), 6)
  }

說明

• 上面的函數 findallpermutationapplyhandler() 可以找到排列，並將給定的處理程序套用到每個組合。
• 但它需要快取之前的 n-1 等級（同時最近的 2 個等級）。
• 我已經避免了最終等級的緩存，因為沒有更多層級依賴它。

問題

• 1. 是否可以避免快取最近2個等級？

     （又名，讓空間複雜度為o(1) 或o(n)，甚至我猜o(n^2) 更好）。 。

• 1. 但這對我來說似乎不可能，因為等級 i 是基於等級 i-1 的，對吧？
• 1. 如果是的話，是否有更好的演算法來降低空間複雜度？迭代是首選（而不是遞歸）。

正確答案

聽起來您正在尋找Pandita 演算法

#這是一種以字典順序迭代產生陣列所有排列的簡單方法。

但是，它要求您可以對陣列的元素進行排序。如果不能（因為它們是泛型類型），那麼您可以建立所有陣列索引的輔助數組，並產生其排列。

以上是在排列上應用處理程序，而不需要級別快取？的詳細內容。更多資訊請關注PHP中文網其他相關文章！