Bagaimanakah std::next_permutation Menemui Permutasi Leksikografik Seterusnya?

Cara std::next_permutation Berfungsi

std::next_permutation ialah fungsi dalam C Standard Template Library (STL) yang menyusun semula urutan ke dalam permutasi leksikografik seterusnya yang lebih besar. Untuk memahami pelaksanaannya, adalah berguna untuk memvisualisasikan urutan sebagai nombor yang setiap elemen mewakili digit.

Logik Teras

Algoritma beroperasi mengikut prinsip berikut:

• Cari Pivot: Bermula dari penghujung jujukan, ia mencari elemen pertama (i) yang kurang daripada elemen di sebelah kanannya (j). Ini menunjukkan bahawa digit di sebelah kanan i adalah dalam tertib menurun.
• Tukar dan Songsang: Sebaik sahaja i ditemui, ia mencari dari hujung untuk elemen pertama (k) iaitu lebih besar daripada i. Elemen ini ditukar dengan i, meletakkannya di hadapan. Elemen selebihnya di sebelah kanan j (dari j ke hujung) kemudiannya diterbalikkan.
• Naikkan Pivot: Jika pivot ditemui (i bukan permulaan), proses itu berulang dengan mengurangkan i dan j.
• Terbalik dan Keluar: Jika pivot tidak dapat ditemui (i ialah permulaan), jujukan diterbalikkan dan fungsi mengembalikan palsu, menunjukkan tiada pilih atur lagi adalah mungkin.

Pembolehubah dalam Kod

• i: Mewakili elemen pangsi paling kiri.
• j: Mewakili unsur di sebelah kanan i yang kurang daripada i.
• k: Mewakili unsur dari kanan yang lebih besar daripada i dan kehendak ditukar dengan i.

Contoh

Pertimbangkan urutan: 1, 3, 2, 4.

• Cari Pangsi: i pada mulanya ditetapkan kepada 4, tetapi memandangkan 4 lebih besar daripada atau sama dengan 2, kita beralih ke i = 2. Oleh kerana 2 kurang daripada 4, i ialah pangsi.
• Tukar dan Songsang: j ditetapkan kepada 3 dan k ditetapkan kepada 1, iaitu elemen pertama dari kanan yang lebih besar daripada 2. 1 ditukar dengan 2, menghasilkan 1, 2, 3 , 4. Baki elemen dari j ke hujung (2, 3, 4) diterbalikkan, memberikan 1, 2, 4, 3.
• Naikkan Pivot: i dikurangkan kepada 1 (j sudah ditetapkan kepada 2). Memandangkan 1 kurang daripada 2, proses itu berulang.
• Cari Pangsi: i dikurangkan kepada elemen pertama (permulaan), menunjukkan bahawa pangsi tidak boleh ditemui.
• Terbalik dan Keluar: Urutan diterbalikkan kepada keadaan asalnya 1, 2, 3, 4 dan fungsi mengembalikan palsu, menunjukkan bahawa tiada pilih atur lagi boleh dilakukan.

Atas ialah kandungan terperinci Bagaimanakah std::next_permutation Menemui Permutasi Leksikografik Seterusnya?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!