在排列上应用处理程序，没有级别缓存？

Question

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

---

代码

（在

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个级别）.
• 我已经避免了 final 级别的缓存，因为没有更多级别依赖于它。

---

问题

• 1. 是否可以避免最近2级的缓存？
     （又名。使空间复杂性

     O(1)

     或

     O(n)

     ，甚至

     O(n^2)

     我猜要好得多）.
• 2. 但这对我来说似乎是不可能的，因为等级

     i

     是基于等级

     i-1

     的，对吧？
• 3. 如果是这样，是否有更好的算法来降低空间复杂度？迭代是首选（比递归）.

Answer 1

听起来你在找Pandita的算法

这是一种以字典顺序迭代生成数组所有排列的简单方法。

但是，它要求您可以对数组的元素进行排序。如果你不能（因为它们是通用类型），那么你可以创建所有数组索引的辅助数组，并生成它的排列。

Answer 2

根据 Matt Timmermans 的回答，我实现了

Pandita's algorithm

，这是 cache-free & in-order.

---

代码

（在

go

）

• 按顺序查找排列：

  // find all permutation of []T, in order, using Pandita's algorithm,
  // apply given handler on each combination, and return count only,
  // repeated elements: it also handle the case with repeated elements, aka. it won't generate repeated combination,
  // refer:   https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order
  func FindAllPermutationInOrderApplyHandler[T constraints.Ordered](ts []T, handler func([]T)) int {
      slices.Sort(ts)
      size := len(ts)
  
      n := 1 // include initial combination,
      handler(ts)
  
      for {
          var k int
          for k = size - 2; ; k-- { // find k,
              if k < 0 { // done
                  return n
              }
              if ts[k] < ts[k+1] {
                  n++
                  break
              }
          }
          valueK := ts[k]
  
          var l int
          for l = size - 1; ; l-- { // find l,
              if ts[l] > valueK {
                  break
              }
          }
  
          ts[k], ts[l] = ts[l], ts[k] // swap k & l,
  
          sc := (size - 1 - k) >> 1
          maxLeft := k + sc
          for left, right := k+1, size-1; left <= maxLeft; left, right = left+1, right-1 { // reverse ts[k+1:],
              ts[left], ts[right] = ts[right], ts[left]
          }
  
          handler(ts)
      }
  }
  

• 测试用例（简单）：

  func TestFindAllPermutationInOrderApplyHandler(t *testing.T) {
      runOnce_FindAllPermutationInOrderApplyHandler_print(t, []int{0, 1, 2}, 6)
  
      // input not ordered,
      runOnce_FindAllPermutationInOrderApplyHandler_print(t, []int{1, 2, 0}, 6)
  
      /* corner */
      // empty
      runOnce_FindAllPermutationInOrderApplyHandler_print(t, []int{}, 1)
      // 1
      runOnce_FindAllPermutationInOrderApplyHandler_print(t, []int{0}, 1)
  }
  
  func TestFindAllPermutationInOrderApplyHandlerRepeatedEle(t *testing.T) {
      runOnce_FindAllPermutationInOrderApplyHandler_print(t, []int{0, 1, 2, 2}, 12)           // A(4) / a(2)
      runOnce_FindAllPermutationInOrderApplyHandler_print(t, []int{0, 1, 2, 2, 2}, 20)        // A(5) / a(3)
      runOnce_FindAllPermutationInOrderApplyHandler_print(t, []int{0, 1, 2, 2, 2, 3, 3}, 420) // A(7) / (A(3) * A(2))
  }
  
  func runOnce_FindAllPermutationInOrderApplyHandler_print[T constraints.Ordered](t *testing.T, ts []T, expectedN int) {
      fmt.Printf("\n%v:\n", ts)
      assert.Equal(t, FindAllPermutationInOrderApplyHandler(ts, func(comb []T) {
          fmt.Printf("\t%v\n", comb)
      }), expectedN)
  }
  

---

复杂性

• 时间：

  O(n!)

  或

  O(n! * n)

  // TODO：不确定，
  维基百科说：

  3 comparisons and 1.5 swaps per permutation

• 空间：

  O(1)

  
  因为它改变了地方。

---

重复元素

它也处理重复元素的情况，又名。它不会产生重复的组合。

要计算总计数，对于每个重复的组，应该除以

A(group's size)

，公式：

A(n) / (A(r1) * A(r2) * .. * A(rx))