Bagaimanakah Kita Boleh Mencari Permutasi ke-N dengan Cekap Tanpa Brute Force?

Mencari Pilihatur ke-n tanpa Kekuatan Brute

Memandangkan pilihatur yang diwakili oleh tatasusunan unsur, adakah mungkin untuk mengira pilihatur ke-n dengan cekap tanpa mengira setiap pilihatur di antaranya?

Jawapannya terletak pada penguraian faktorial. Pertimbangkan susunan permutasi leksikografi. Dengan memecahkan indeks pilih atur kepada pecahan faktorial, kita boleh memperoleh pilih atur khusus.

1. Lakukan pemfaktoran dengan nombor pemfaktoran, bermula dari pemfaktoran tertinggi.
2. Penilaian mewakili indeks dalam tatasusunan pilih atur. Laraskannya untuk mengambil kira nilai sebelumnya yang mungkin sama atau lebih rendah.

Pendekatan ini membolehkan kita melompat terus ke pilih atur yang diingini tanpa memerlukan lelaran kekerasan.

Sebagai contoh , diberi tatasusunan {A, B, C}, penguraian faktorial untuk pilih atur ke-3 saiz 2 ialah (2! * 0) (1! * 1) = (2 * 0) (1 * 1) = 1. Ini sepadan dengan elemen pertama (B) diikuti dengan elemen ke-0 (A).

Pelaksanaan C berikut menunjukkan teknik ini:

void ithPermutation(const int n, int i) {
    int *fact = (int *)calloc(n, sizeof(int));
    int *perm = (int *)calloc(n, sizeof(int));

    // Compute factorial numbers
    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 = i % fact[n - 1 - k];
    }

    // Readjust values to obtain the 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++) {
        printf("%d ", perm[k]);
    }
    printf("\n");

    free(fact);
    free(perm);
}

Memanggil ithPermutation(10, 3628799) mengembalikan pilih atur terakhir bagi sepuluh elemen:

9 8 7 6 5 4 3 2 1 0

Atas ialah kandungan terperinci Bagaimanakah Kita Boleh Mencari Permutasi ke-N dengan Cekap Tanpa Brute Force?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!