How Can We Efficiently Find the nth Permutation Without Brute Force?

Finding nth Permutation without Brute Force

Given a permutation represented by an array of elements, is it possible to efficiently calculate the nth permutation without computing every permutation in between?

The answer lies in factorial decomposition. Consider the lexicographical order of permutations. By breaking down the index of the permutation into factorial fractions, we can derive the specific permutation.

1. Perform a factorization with factorial numbers, starting from the highest factorial.
2. The quotients represent the indices in the permutation array. Adjust them to account for previous values that may be equal or lower.

This approach allows us to jump directly to the desired permutation without the need for brute force iteration.

For example, given an array {A, B, C}, the factorial decomposition for the 3rd permutation of size 2 would be (2! * 0) (1! * 1) = (2 * 0) (1 * 1) = 1. This corresponds to the 1st element (B) followed by the 0th element (A).

The following C implementation demonstrates this 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);
}

Calling 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 nth Permutation Without Brute Force?. For more information, please follow other related articles on the PHP Chinese website!