Bagaimanakah algoritma std::next_permutation berfungsi untuk mencari pilih atur leksikografi yang lebih besar bagi suatu jujukan?

std::next_permutation Penjelasan Pelaksanaan

Algoritma std::next_permutation mengira pilih atur leksikografik seterusnya yang lebih besar daripada jujukan tertentu. Memahami pelaksanaannya adalah penting untuk memahami gelagatnya.

Garis Algoritma

Algoritma berulang mengikut urutan dari kanan ke kiri, mencari "naik" paling kiri (iaitu. , elemen yang lebih kecil daripada penggantinya). Jika tiada ascender ditemui, ini bermakna jujukan dalam susunan menurun, dalam kes ini ia membalikkan jujukan untuk mendapatkan pilih atur terkecil.

Jika tidak, algoritma diteruskan dengan mencari elemen terkecil dalam jujukan ke kanan daripada ascender (dipanggil "k"). Elemen ini kemudian ditukar dengan ascender. Akhir sekali, elemen di sebelah kanan ascender diterbalikkan untuk mengekalkan susunan yang semakin berkurangan.

Peranan Pembolehubah

• i: Mata kepada elemen semasa sedang diperiksa.
• j: Menunjuk kepada elemen sejurus sebelum i.
• k: Menunjuk kepada unsur terkecil dalam jujukan di sebelah kanan i apabila i adalah penaik.

Aliran Gelung

Gelung berulang sehingga saya mencapai permulaan jujukan (mula). Dalam setiap lelaran:

1. Jika i bukan ascender, ia mengurangkan i dan j.
2. Jika i ialah ascender, ia mencari unsur terkecil di sebelah kanan i (k ), menukarnya dengan i dan menterbalikkan semuanya di sebelah kanan i.

Contoh

Pertimbangkan urutan {1, 2, 4, 3} .

• Lelaran 1: i pada mulanya pada 3. j ialah pada 2. Sejak 3 < 4 (i < j), i ialah penaik.
• Lelaran 2: k didapati 2. 3 ditukar dengan 2. {1, 3, 4, 2} . Unsur di sebelah kanan 3 (4 dan 2) diterbalikkan. {1, 3, 2, 4}.
• Lelaran 3: i dikurangkan dan j dikurangkan. i kini pada 2. j ialah pada 1. 2 < 3, jadi i ialah penaik.
• Lelaran 4: k didapati 1. 2 ditukar dengan 1. {1, 2, 4, 3}. Unsur di sebelah kanan 2 (4 dan 3) diterbalikkan. {1, 2, 3, 4}.
• Lelaran 5: i dikurangkan dan j dikurangkan. i kini berada pada 1. j berada pada permulaan jujukan. Oleh kerana tiada lagi ascenders, urutannya diterbalikkan. {4, 3, 2, 1}.

Atas ialah kandungan terperinci Bagaimanakah algoritma std::next_permutation berfungsi untuk mencari pilih atur leksikografi yang lebih besar bagi suatu jujukan?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!