JavaScript Coding Test Course, Finding the Order of Permutations

Problem Description

There is a problem of finding the index of a specific permutation among the permutations that can be made from the given numbers.

For example, when the numbers 1, 2, and 3 are given, all the possible permutations are as follows:

The question is to find out the index of a specific number’s permutation. In the above example, 231 corresponds to the 4th position.

Input Format

The first line contains the number of digits n (1 ≤ n ≤ 10).

The second line contains n natural numbers. (Each number is a different natural number from 1 to n.)

The third line contains the desired permutation index k (1 ≤ k ≤ n!).

Output Format

Print the desired permutation.

Problem Solving

Approach

To solve this problem, we define the following steps:

Generate all combinations of the numbers to create a list of permutations.
Find the desired permutation in the list of permutations.

Permutation Generation Algorithm

Here, we will describe the process of generating permutations and finding a specific order using JavaScript. We will use the DFS (Depth-First Search) method to generate permutations.

JavaScript Code

        
function getPermutations(arr) {
    const result = [];
    
    const backtrack = (current, remaining) => {
        if (remaining.length === 0) {
            result.push(current);
            return;
        }
        
        for (let i = 0; i < remaining.length; i++) {
            const newCurrent = [...current, remaining[i]];
            const newRemaining = [...remaining.slice(0, i), ...remaining.slice(i + 1)];
            backtrack(newCurrent, newRemaining);
        }
    };
    
    backtrack([], arr);
    return result;
}

function findPermutation(n, nums, k) {
    const permutations = getPermutations(nums);
    return permutations[k - 1].join('');
}

// Example input
const n = 3;
const nums = [1, 2, 3];
const k = 4;

// Output
console.log(findPermutation(n, nums, k)); // 231

Code Explanation

The above code consists of two functions:

getPermutations: Generates all permutations of the given array.
findPermutation: Returns the permutation corresponding to the desired index.

Detailed Explanation of getPermutations Function

This function generates permutations recursively:

Select one of the elements from the current array and add it to the current combination.
Create a new array with the remaining elements, excluding the selected element, and proceed with the recursive call.
Repeat this process until all elements are selected, and add the completed permutation to the result.

Detailed Explanation of findPermutation Function

This function goes through the following steps:

Generates all permutations for the given number array.
Finds the permutation corresponding to the k-1 index in the generated permutation array and returns it as a string.

Time Complexity

The time complexity of this algorithm is O(n!). Since it generates all permutations, the calculation time can become very long as the number of digits increases. However, since the value of n is limited to 10 or less, the problem can be solved at a practical level.

Conclusion

Now you have learned how to create permutations and find a specific ordered permutation. This is one of the types of problems that frequently appear in coding tests, so practice until you are fully proficient.

In the next session, I will return with another algorithm problem. Thank you!