Jika Anda menjelaskan secara singkat apa urutan leksikografis, ini mengurutkan dalam urutan abjad. Yaitu urutan karakter - AAA → AAB → AAC → AAD → ……… → WWW - diurutkan dalam urutan abjad (atau dalam kamus kasus kami).
Bayangkan Anda memiliki urutan karakter yang terbatas, misalnya 0, 1, 2, 5, 3, 3, 0 dan Anda perlu menemukan semua permutasi yang mungkin dari karakter-karakter ini. Yang paling intuitif, tetapi juga yang paling sulit, adalah algoritma rekursif, ketika kita memilih karakter pertama dari urutan, kemudian pilih yang kedua, ketiga, dll, secara rekursif, sampai semua karakter dari urutan dipilih. Jelas bahwa kompleksitas dari algoritma tersebut adalah O (n!).
Tetapi ternyata algoritma paling sederhana untuk menghasilkan semua permutasi dalam urutan leksikografis adalah memulai dengan yang terkecil dan berulang kali menghitung permutasi berikutnya. Mari kita lihat bagaimana melakukannya.
Sama seperti ketika menghitung nilai integer berikutnya, kita harus mencoba meningkatkan sisi kanan urutan dan membiarkan sisi kiri tidak berubah.
Sebagai contoh, ambil urutan di atas - (0, 1, 2, 5, 3, 3, 0). Untuk mendapatkan urutan lebih tinggi dari yang asli, cukup untuk mengatur ulang elemen pertama dan kedua di tempat, tetapi ini tidak perlu, karena Anda dapat mengatur ulang yang kedua dan ketiga dan mendapatkan urutan lebih dekat dalam urutan menaik. yang akan membawa kita ke permutasi lebih dekat berikutnya, dll.
Algoritma yang paling optimal dalam hal ini adalah sebagai berikut:
- Pertama-tama, Anda perlu menemukan akhiran non-meningkat terbesar. Dalam contoh di atas, ini akan menjadi - (5, 3, 3, 0). Jika Anda mencoba membuat permutasi dalam urutan ini, maka itu tidak akan lebih tinggi dari yang asli.
Perlu dikatakan bahwa Anda dapat menemukan urutan ini dalam waktu O (n) dengan melihat urutan dari kiri ke kanan. - Elemen berikutnya dari suffix adalah titik pivot. Dalam kasus kami, ini adalah 2. Titik pivot akan selalu kurang dari elemen pertama dari suffix. Ini berarti bahwa dalam sufiks pasti akan ada elemen yang melebihi titik pivot dan jika kita mengubah titik pivot ke elemen terkecil dari sufiks yang melebihi elemen pivot point support - kita akan mendapatkan urutan yang melebihi yang asli - dalam kasus kita akan menjadi (0, 1, 3, 5 , 3, 2, 0).
Yaitu hasil operasi ini akan menjadi awalan naik minimum yang mungkin.
- Dan pada langkah terakhir, kita perlu mengurutkan suffix dalam urutan menaik. Yaitu kita mendapatkan sufiks sekecil mungkin. Dalam contoh kita, itu akan menjadi (0, 2, 3, 5) dan seluruh urutan akan terlihat seperti (0, 1, 3, 0, 2, 3, 5).
Nilai ini akan menjadi
penataan ulang leksikografis berikutnya.
Adapun aplikasi praktis dari algoritma, untuk semua waktu pekerjaan saya, saya tidak pernah membutuhkannya, tetapi untuk wawancara dengan Uber mereka berpikir sebaliknya :))
Untuk kesederhanaan, semua kode akan ditulis dalam Go, dan saya pikir mudah bagi siapa saja untuk menerjemahkannya ke bahasa pemrograman lain.Terima kasih banyak kepada PYXRU dan 646f67 yang telah menyodok saya dengan kemungkinan optimasi algoritma - untuk menghitung permutasi untuk kompleksitas linier hanya dengan melakukan sufiks terbalik.
func NextPermutationAlgorithm(w string) string { l := len(w) b := []byte(w) r := "no answer" for i:=l-1; i>0 ; i--{ if b[i-1] < b[i] { pivot := i for j := pivot; j < l; j++ { if b[j] <= b[pivot] && b[i-1] < b[j] { pivot = j } } b[i-1], b[pivot] = b[pivot], b[i-1] for j := l-1; i < j; i, j = i+1, j-1 { b[i], b[j] = b[j], b[i] } r = string(b) break } } return r }