Apply handler on permutation, without cache of levels?

Question

I want to write a function that apply given handler to all permutation of input, without return the whole permutation.

---

Code

(in go)

• Find permutation:

  // 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
  }
  

• Test case (simple):

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

---

Explanation

• The above function FindAllPermutationApplyHandler() can find permutation, and apply given handler to each combination.
• But it need to cache the previous n-1 levels (most recent 2 levels at the same time).
• I've already avoided cache of the final level, since no more level depends on it.

---

Questions

• 1. Is it possible to avoid cache of the recent 2 levels ?
     (aka. make the space complexity O(1) or O(n), or even O(n^2) is much better I guess).
• 2. But it seems impossible to me, since level i is based on level i-1, right?
• 3. If so, is there a better algorithm that reduce the space complexity? And iteration is preferred (than recursion).

Answer 1

It sounds like you're looking for Pandita's algorithm

This is a simple way to iteratively generate all permutations of an array in lexicographic order.

It requires that you can order elements of your array, however. If you can't (because they're of generic type), then you can make a secondary array of all the array indexes, and generate permutations of that.