How Can We Efficiently Find the n-th Permutation of a Set?

Efficient Algorithm for Identifying n-th Permutation

Given an array of elements representing a permutation, this question explores the possibility of an algorithm that efficiently calculates the n-th permutation without computing all preceding ones.

Factoradic Permutation Decomposition

The solution leverages the concept of factoradic decomposition. By performing successive divisions by factorials, it decomposes the permutation index into a sequence of quotients. This sequence represents the desired permutation.

Adjusting Quotients

However, the initial quotients disregard the impact of previous values. Thus, an adjustment step is necessary. For each quotient, it increments the value by the count of smaller or equal preceding quotients.

Implementation

A C implementation of the algorithm is provided below:

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

Example

For instance, ithPermutation(10, 3628799) returns the last permutation of ten elements:

9 8 7 6 5 4 3 2 1 0

The above is the detailed content of How Can We Efficiently Find the n-th Permutation of a Set?. For more information, please follow other related articles on the PHP Chinese website!