Bagaimanakah Kita Boleh Mendapatkan Permutasi ke-n Set dengan Cekap?

Algoritma Cekap untuk Mengenalpasti Pilihalih ke-n

Memandangkan susunan elemen yang mewakili pilihatur, soalan ini meneroka kemungkinan algoritma yang cekap mengira pilihatur ke-n tanpa mengira semua sebelumnya satu.

Penguraian Pilihatur Faktoradik

Penyelesaian memanfaatkan konsep penguraian faktoradik. Dengan melakukan pembahagian berturut-turut oleh faktorial, ia menguraikan indeks pilih atur kepada urutan hasil bahagi. Urutan ini mewakili pilih atur yang diingini.

Pelarasan Petik

Walau bagaimanapun, hasil bagi awal mengabaikan kesan nilai sebelumnya. Oleh itu, langkah pelarasan adalah perlu. Bagi setiap hasil bagi, ia menambah nilai mengikut kiraan nilai bahagi yang lebih kecil atau sama.

Pelaksanaan

Pelaksanaan C bagi algoritma disediakan di bawah:

void ithPermutation(const int n, int i) {
    int *fact = new int[n], *perm = new int[n];

    // Compute factorials
    fact[0] = 1;
    for (int k = 1; k < n; k++)
        fact[k] = fact[k - 1] * k;

    // Compute factorial code
    for (int k = 0; k < n; k++) {
        perm[k] = i / fact[n - 1 - k];
        i %= fact[n - 1 - k];
    }

    // Adjust values for permutation
    for (int k = n - 1; k > 0; k--)
        for (int j = k - 1; j >= 0; j--)
            if (perm[j] <= perm[k])
                perm[k]++;

    // Print permutation
    for (int k = 0; k < n; k++)
        cout << perm[k] << " ";
    cout << "\n";

    delete[] fact;
    delete[] perm;
}

Contoh

Untuk contoh, ithPermutation(10, 3628799) mengembalikan pilihatur terakhir bagi sepuluh elemen:

9 8 7 6 5 4 3 2 1 0

Atas ialah kandungan terperinci Bagaimanakah Kita Boleh Mendapatkan Permutasi ke-n Set dengan Cekap?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!