Gunakan pengendali pada susunan tanpa caching tahap?

Kandungan soalan

Saya ingin menulis fungsi yang menggunakan pengendali yang diberikan kepada semua pilih atur input tanpa mengembalikan keseluruhan pilih atur.

Kod

(dalam go)

• Cari susunan:

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

• Kes Ujian(Mudah):

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

Arahan

• Fungsi findallpermutationapplyhandler() di atas mencari pilih atur dan menggunakan pengendali yang diberikan pada setiap kombinasi.
• Tetapi ia perlu cache n-1 tahap sebelumnya (2 tahap terkini pada masa yang sama) .
• Saya telah mengelakkan caching pada peringkat akhir kerana tiada lagi tahap bergantung padanya.

Soalan

• 1. Adakah mungkin untuk mengelakkan cache 2 tahap terakhir?

     (aka, jadikan kerumitan ruang o(1) 或 o(n)，甚至我猜 o(n^2) lebih baik). .

• 1. Tetapi itu nampak mustahil bagi saya kerana tahapnya i 是基于级别 i-1, bukan?
• 1. Jika ya, adakah terdapat algoritma yang lebih baik untuk mengurangkan kerumitan ruang? Lelaran lebih disukai (bukan pengulangan).

Jawapan Betul

Nampaknya anda sedang mencariAlgoritma Pandita

Ini ialah cara mudah untuk mengulangi semua pilih atur tatasusunan dalam susunan leksikografik.

Walau bagaimanapun, ia memerlukan anda boleh mengisih elemen tatasusunan. Jika tidak (kerana ia adalah jenis generik), maka anda boleh mencipta tatasusunan tambahan bagi semua indeks tatasusunan dan menjana pilih aturnya.

Atas ialah kandungan terperinci Gunakan pengendali pada susunan tanpa caching tahap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!