Apply handler on permutation, without cache of levels?

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).

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.

According to Matt Timmermans's answer, I implemented the Pandita's algorithm, which is cache-free & in-order.

Code

(in go)

• Find permutation, in order:

  package permutation_util
  import (
  "fmt"
  "golang.org/x/exp/constraints"
  "golang.org/x/exp/slices"
  )
  // will sort first, in default order,
  func FindAllPermutationInOrderApplyHandlerDefaultSort[T constraints.Ordered](ts []T, handler func(ts []T, isComb []int)) int {
  return FindAllPermutationInOrderApplyHandlerCustomizedSort(ts, handler, nil)
  }
  // sort reversely,
  func FindAllPermutationInOrderApplyHandlerReversedSort[T constraints.Ordered](ts []T, handler func(ts []T, isComb []int)) int {
  return FindAllPermutationInOrderApplyHandlerCustomizedSort(ts, handler, func(a, b T) bool {
  return a > b // reversed,
  })
  }
  // sort by given compare function,
  func FindAllPermutationInOrderApplyHandlerCustomizedSort[T constraints.Ordered](ts []T, handler func(ts []T, isComb []int), less func(a, b T) bool) int {
  if less != nil {
  slices.SortFunc(ts, less)
  } else {
  slices.Sort(ts)
  }
  return FindAllPermutationInOrderApplyHandlerNoSort(ts, handler)
  }
  // find all permutation of []T, in order, using Pandita's algorithm,
  // ts should be already sorted, in the order you wish,
  // 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 FindAllPermutationInOrderApplyHandlerNoSort[T constraints.Ordered](ts []T, handler func(ts []T, isComb []int)) int {
  is := genInitialIs(ts)
  fmt.Printf("initial order: %v\n", is)
  n := 1 // include initial combination,
  handler(ts, is)
  size := len(ts)
  for {
  var k int
  for k = size - 2; ; k-- { // find k,
  if k < 0 { // done
  return n
  }
  if is[k] < is[k+1] {
  n++
  break
  }
  }
  valueK := is[k]
  var l int
  for l = size - 1; ; l-- { // find l,
  if is[l] > valueK {
  break
  }
  }
  is[k], is[l] = is[l], is[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 is[k+1:],
  is[left], is[right] = is[right], is[left]
  }
  handler(ts, is)
  }
  }
  // generate initial index, and handle repeated elements, to avoid repeated combination,
  // e.g [7 11 11 13] -> [0 1 1 3]
  func genInitialIs[T constraints.Ordered](ts []T) []int {
  size := len(ts)
  is := make([]int, size)
  for i, ir := 0, 0; i < size; i++ { // generation initial order,
  if i == 0 || ts[i] != ts[i-1] {
  ir = i
  }
  is[i] = ir
  }
  return is
  }
  

• Test case:

  package permutation_util
  import (
  "fmt"
  "github.com/stretchr/testify/assert"
  "golang.org/x/exp/constraints"
  "testing"
  )
  // default order
  func Test_FindAllPermutationInOrderApplyHandlerDefaultSort(t *testing.T) {
  runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{0, 1, 2}, 6)
  // input not ordered,
  runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{1, 2, 0}, 6)
  /* corner */
  // empty
  runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{}, 1)
  // 1
  runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{0}, 1)
  }
  func Test_FindAllPermutationInOrderApplyHandlerDefaultSort_RepeatedEle(t *testing.T) {
  runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{0, 1, 2, 2}, 12)           // A(4) / a(2)
  runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{0, 1, 2, 2, 2}, 20)        // A(5) / a(3)
  runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{0, 1, 2, 2, 2, 3, 3}, 420) // A(7) / (A(3) * A(2))
  runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print(t, []int{11, 13, 7, 11}, 12) // A(4) / a(2)
  }
  func runOnce_FindAllPermutationInOrderApplyHandlerDefaultSort_print[T constraints.Ordered](t *testing.T, ts []T, expectedN int) {
  fmt.Printf("\n%v:\n", ts)
  assert.Equal(t, FindAllPermutationInOrderApplyHandlerDefaultSort(ts, func(ts []T, isComb []int) {
  tsComb := make([]T, len(ts))
  for i := 0; i < len(ts); i++ {
  tsComb[i] = ts[isComb[i]]
  }
  fmt.Printf("\t%v\n", tsComb)
  }), expectedN)
  }
  // reversed order,
  func TestFindAllPermutationInOrderApplyHandler_reversed(t *testing.T) {
  runOnce_FindAllPermutationInOrderApplyHandlerCustomizedSort_reversedPrint(t, []int{0, 1, 2}, 6)
  }
  func runOnce_FindAllPermutationInOrderApplyHandlerCustomizedSort_reversedPrint[T constraints.Ordered](t *testing.T, ts []T, expectedN int) {
  fmt.Printf("\n%v:\n", ts)
  assert.Equal(t, FindAllPermutationInOrderApplyHandlerReversedSort(ts, func(ts []T, isComb []int) {
  tsComb := make([]T, len(ts))
  for i := 0; i < len(ts); i++ {
  tsComb[i] = ts[isComb[i]]
  }
  fmt.Printf("\t%v\n", tsComb)
  }), expectedN)
  }
  

Complexity

• Time: O(n!) or O(n! * n) // TODO: not sure,
  wikipedia says: 3 comparisons and 1.5 swaps per permutation
• Space: O(1)
  Since it change in place.

Repeated elements

It also handle the case with repeated elements, aka. it won't generate repeated combination.

To figure out total count, for each repeated group, should divide A(group's size), formula:
> A(n) / (A(r1) * A(r2) * .. * A(rx))