Handler nach Vereinbarung ohne Level-Caching anwenden?

Frageninhalt

Ich möchte eine Funktion schreiben, die einen bestimmten Handler auf alle Eingabepermutationen anwendet, ohne die gesamte Permutation zurückzugeben.

Code

(in go)

• Arrangement finden:

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

• Testfall(Einfach):

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

Anleitung

• Die obige Funktion findallpermutationapplyhandler() findet Permutationen und wendet den angegebenen Handler auf jede Kombination an.
• Aber es muss die vorherigen n-1 Level (die letzten 2 Level gleichzeitig) zwischenspeichern.
• Ich habe das Caching auf der letzten Ebene vermieden, da keine weiteren Ebenen davon abhängen.

Frage

• 1. Ist es möglich, das Zwischenspeichern der letzten beiden Ebenen zu vermeiden?

     (also, die Raumkomplexität verbessern o(1) 或 o(n)，甚至我猜 o(n^2)). .

• 1. Aber das scheint mir aufgrund des Niveaus unmöglich zu sein i 是基于级别 i-1, oder?
• 1. Wenn ja, gibt es einen besseren Algorithmus zur Reduzierung der Raumkomplexität? Iteration wird bevorzugt (statt Rekursion).

Richtige Antwort

Klingt, als ob Sie nach dem Pandita-Algorithmus

suchen

Dies ist eine einfache Möglichkeit, alle Permutationen eines Arrays in lexikografischer Reihenfolge zu durchlaufen.

Allerdings ist es erforderlich, dass Sie die Elemente des Arrays sortieren können. Wenn nicht (da es sich um generische Typen handelt), können Sie ein Hilfsarray aller Array-Indizes erstellen und deren Permutationen generieren.

Das obige ist der detaillierte Inhalt vonHandler nach Vereinbarung ohne Level-Caching anwenden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!