How Can We Find the N-th Permutation of a Set Directly Without Generating All Preceding Permutations?

Getting the n-th Permutation Directly

The task is to find the n-th permutation of a set of elements without explicitly computing all the previous permutations. This can be achieved using a clever algorithm called the Factoradic Algorithm.

The Factoradic Algorithm leverages the factorial decomposition of the permutation index. By repeatedly performing Euclidian division with factorial numbers, we obtain a set of quotients that represent the permutation.

Here's how the algorithm works:

1. Factorial Decomposition: Divide the permutation index n by the factorial of (n-1)!, (n-2)!, and so on. The quotients are stored in an array.
2. Permutation Representation: Each quotient represents the index of the element chosen from the remaining elements.
3. Adjustment: Since the quotients do not consider preceding values, they need to be adjusted to reflect the correct permutation. Increment each quotient by the number of preceding quotients that are lower or equal to it.

For instance, let's find the 3rd permutation of {'A', 'B', 'C'}.

• n = 3
• Quotients: [1, 0, 0]
• Adjusted Quotients: [1, 0, 1]

The permutation is thus 'B', 'A', 'C', which is indeed the 3rd permutation of the given set.

The provided C code implements the Factoradic Algorithm, demonstrating how to obtain the n-th permutation directly without computing the previous ones.

The above is the detailed content of How Can We Find the N-th Permutation of a Set Directly Without Generating All Preceding Permutations?. For more information, please follow other related articles on the PHP Chinese website!