Pilih atur panjang n ialah koleksi tertib tanpa ulangan nombor 1, 2, ..., n. Contohnya, [3, 1, 2] dan [5, 4, 3, 2, 1] ialah pilih atur, tetapi [1, 2, 1, 3] dan [1, 2, 4] bukan.
Jika tugas itu dikurangkan kepada fakta bahawa ia adalah perlu untuk mengulangi semua pilih atur panjang n, maka anda boleh menggunakan mekanisme yang mudah dalam C ++, yang dipanggil "next_permutation".
Anda boleh membaca lebih lanjut mengenainya dalam dokumentasi, tetapi maksudnya ialah fungsi ini mengubah tatasusunan yang diluluskan kepada pilih atur seterusnya dalam susunan leksikografi (yang umumnya jelas dan namanya).
Untuk menggunakan next_permutation, anda perlu memasukkan perpustakaan algoritma (iaitu tulis #include <algorithm> pada permulaan program)
Contoh:
vektor arr;
arr = { 1, 2, 3}; // tatasusunan ialah [1, 2, 3]
next_permutation(arr.begin(), arr.end()); // lulus keseluruhan tatasusunan ke fungsi
// array kini [1, 3, 2]
arr = { 2, 3, 1}; // tatasusunan ialah [2, 3, 1]
next_permutation(arr.begin(), arr.end()); // lulus keseluruhan tatasusunan ke fungsi
// array kini [3, 1, 2]
next_permutation(arr.begin() + 1, arr.begin() + 3); // adalah mungkin untuk menggunakan fungsi pada sebahagian daripada tatasusunan, tetapi dalam amalan ini jarang diperlukan
// array kini [3, 2, 1]
Dalam kes ini, fungsi mempunyai nilai pulangan boolean yang benar jika pilih atur seterusnya dijana dan palsu jika tiada satu lagi (kes apabila pilih atur maksimum dalam susunan leksikografi diserahkan kepada fungsi).
Ini memungkinkan untuk menggunakan fungsi dalam gelung, yang akan membolehkan kami mengulangi semua pilih atur sekali gus. Disebabkan oleh pengindeksan 0, dalam praktiknya selalunya lebih mudah untuk bekerja dengan pilih atur nombor dari 0 hingga n - 1, walaupun pilih atur secara rasmi mengandungi nombor dari 1 hingga n. Tetapi mujurlah, ini tidak membawa kepada tindanan tambahan dalam kod, kerana fungsi next_permutation disesuaikan dengan pilih atur 0-indeks (dan juga elemen pendua dalam tatasusunan, tetapi anda boleh mengetahui lebih lanjut sendiri).
Secara umum, kod untuk lelaran ke atas semua pilih atur kelihatan seperti ini:
intn; // saiz pilihatur
vektorperm(n); // perm ialah singkatan untuk "permutation", i.e. "permutasi"
untuk (int i = 0; i < n; i++)
perm[i] = i; // mulakan pilih atur awal 0, 1, ..., n - 1
lakukan {
// di dalam gelung kita memproses pilih atur semasa
} manakala (next_permutation(perm.begin(), perm.end())); // jika tiada pilih atur seterusnya, maka tamatkan gelung
Kod ini berjalan dalam O(n! * f(n)), dengan f(n) ialah masa yang anda perlukan untuk memproses satu pilihatur tertentu.