Gunakan pengendali pada susunan tanpa caching tahap?

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

Kod

(dalamgo)

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

  Salin selepas log masuk

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

  Salin selepas log masuk

Arahan

• Fungsifindallpermutationapplyhandler()di atas mencari pilih atur dan menggunakan pengendali yang diberikan pada setiap kombinasi.
• Tetapiia perlu cachen-1tahap sebelumnya(2 tahap terkini pada masa yang sama).
• Saya telah mengelakkan caching pada peringkatakhirkerana tiada lagi tahap bergantung padanya.

Soalan

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

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

• 1. Tetapi itu nampak mustahil bagi saya kerana tahapnyai是基于级别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!