Wie können wir effizient die n-te Permutation einer Menge finden?

Effizienter Algorithmus zur Identifizierung der n-ten Permutation

Gegeben ein Array von Elementen, die eine Permutation darstellen, untersucht diese Frage die Möglichkeit eines Algorithmus, der Berechnet effizient die n-te Permutation, ohne alle vorhergehenden zu berechnen.

Faktoradisch Permutationszerlegung

Die Lösung nutzt das Konzept der faktoradischen Zerlegung. Durch aufeinanderfolgende Divisionen durch Fakultäten wird der Permutationsindex in eine Folge von Quotienten zerlegt. Diese Sequenz stellt die gewünschte Permutation dar.

Anpassen der Quotienten

Die anfänglichen Quotienten berücksichtigen jedoch die Auswirkungen vorheriger Werte. Daher ist ein Anpassungsschritt erforderlich. Für jeden Quotienten wird der Wert um die Anzahl der kleineren oder gleichen vorhergehenden Quotienten erhöht.

Implementierung

Eine C-Implementierung des Algorithmus ist unten angegeben:

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

Beispiel

Zum Beispiel, 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 effizient die n-te Permutation einer Menge finden?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!