在排列上应用处理程序，而不需要级别缓存？

问题内容

我想编写一个函数，将给定的处理程序应用于所有输入排列，而不返回整个排列。

代码

（在 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中文网其他相关文章！