Wie können wir die n-te Permutation effizient und ohne rohe Gewalt finden?

Die n-te Permutation ohne rohe Gewalt finden

Ist es bei einer gegebenen Permutation, die durch ein Array von Elementen dargestellt wird, möglich, die n-te Permutation effizient zu berechnen, ohne jede Permutation dazwischen zu berechnen?

Die Antwort liegt in der faktoriellen Zerlegung. Betrachten Sie die lexikografische Reihenfolge der Permutationen. Indem wir den Index der Permutation in Fakultätsbrüche zerlegen, können wir die spezifische Permutation ableiten.

1. Führen Sie eine Faktorisierung mit Fakultätszahlen durch, beginnend mit der höchsten Fakultät.
2. Die Quotienten repräsentieren die Indizes im Permutationsarray. Passen Sie sie an, um vorherige Werte zu berücksichtigen, die gleich oder niedriger sein können.

Dieser Ansatz ermöglicht es uns, direkt zur gewünschten Permutation zu springen, ohne dass eine Brute-Force-Iteration erforderlich ist.

Zum Beispiel , gegeben ein Array {A, B, C}, wäre die faktorielle Zerlegung für die 3. Permutation der Größe 2 (2! * 0) (1! * 1) = (2 * 0) (1 * 1) = 1. Dies entspricht dem 1. Element (B), gefolgt vom 0. Element (A).

Die folgende C-Implementierung demonstriert diese Technik:

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

Der Aufruf von ithPermutation(10, 3628799) gibt die letzte Permutation von zehn Elementen zurück:

9 8 7 6 5 4 3 2 1 0

Das obige ist der detaillierte Inhalt vonWie können wir die n-te Permutation effizient und ohne rohe Gewalt finden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!