Appliquer le gestionnaire sur l'arrangement sans mise en cache de niveau ?

Contenu de la question

Je souhaite écrire une fonction qui applique un gestionnaire donné à toutes les permutations d'entrée sans renvoyer la permutation entière.

Code

(en go)

• Trouver un 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
  }

• Cas de test(Simple) :

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

Instructions

• La fonction findallpermutationapplyhandler() ci-dessus trouve des permutations et applique le gestionnaire donné à chaque combinaison.
• Mais il doit mettre en cache les n-1 niveaux précédents (les 2 niveaux les plus récents en même temps) .
• J'ai évité la mise en cache au niveau final puisqu'aucun niveau n'en dépend plus.

Question

• 1. Est-il possible d'éviter de mettre en cache les 2 derniers niveaux ?

     (c'est-à-dire améliorer la complexité de l'espace o(1) 或 o(n)，甚至我猜 o(n^2)). .

• 1. Mais ça me semble impossible à cause du niveau i 是基于级别 i-1, non ?
• 1. Si oui, existe-t-il un meilleur algorithme pour réduire la complexité de l'espace ? L'itération est préférable (au lieu de la récursivité).

Réponse correcte

On dirait que vous cherchezAlgorithme Pandita

C'est un moyen simple de parcourir toutes les permutations d'un tableau dans l'ordre lexicographique.

Cependant, cela nécessite que vous puissiez trier les éléments du tableau. Sinon (car ce sont des types génériques), vous pouvez alors créer un tableau auxiliaire de tous les indices du tableau et générer sa permutation.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!