Apply handler on arrangement without level caching?

Question content

I want to write a function that applies a given handler to all input permutations without returning the entire permutation.

Code

(in go)

• Find the arrangement:

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

illustrate

• The above function findallpermutationapplyhandler() can find permutations and apply the given handler to each combination.
• But it requires caching the previous n-1 levels (the most recent 2 levels at the same time) .
• I've avoided the caching of the final level since no more levels depend on it.

question

• 1. Is it possible to avoid caching the last 2 levels?

     (aka, makes the space complexity o(1) or o(n), or even I guess o(n^2) more good). .

• 1. But that seems impossible to me since level i is based on level i-1, right?
• 1. If so, is there a better algorithm to reduce space complexity? Iteration is preferred (instead of recursion).

Correct Answer

Sounds like you are looking forPandita Algorithm

This is a simple way to iterate through all permutations of an array in lexicographic order.

However, it requires that you can sort the elements of the array. If not (because they are generic types), then you can create an auxiliary array of all array indices and generate their permutations.

The above is the detailed content of Apply handler on arrangement without level caching?. For more information, please follow other related articles on the PHP Chinese website!