Comment pouvons-nous trouver efficacement la nième permutation sans force brute ?

Trouver la nième permutation sans force brute

Étant donné une permutation représentée par un tableau d'éléments, est-il possible de calculer efficacement la nième permutation sans calculer chaque permutation intermédiaire ?

La réponse réside dans la décomposition factorielle. Considérons l'ordre lexicographique des permutations. En décomposant l'indice de permutation en fractions factorielles, on peut en déduire la permutation spécifique.

1. Effectuer une factorisation avec des nombres factoriels, en commençant par la factorielle la plus élevée.
2. Les quotients représentent les indices dans le tableau de permutation. Ajustez-les pour tenir compte des valeurs précédentes qui peuvent être égales ou inférieures.

Cette approche nous permet de passer directement à la permutation souhaitée sans avoir besoin d'une itération par force brute.

Par exemple , étant donné un tableau {A, B, C}, la décomposition factorielle pour la 3ème permutation de taille 2 serait (2! * 0) (1! * 1) = (2 * 0) (1 * 1) = 1. Cela correspond au 1er élément (B) suivi du 0ème élément (A).

L'implémentation C suivante démontre cette technique :

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);
}

L'appel de ithPermutation(10, 3628799) renvoie la dernière permutation de dix éléments :

9 8 7 6 5 4 3 2 1 0

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!