Java Coding Test Course, Finding the Order of Permutations

Problem Definition

This problem involves determining the position of a specific number’s permutation in a given number array. For example, when the array is [1, 2, 3], all permutations are listed as follows:

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

For example, for the number 2, when the permutation is 2, 1, 3, this permutation will be in the 3rd position. We will deduce from this information to find out the position of the given number’s permutation.

Problem Approach

To solve this problem, you can follow these steps:

1. Calculate the total number of permutations based on the length of the given array.
2. Calculate the position based on the target permutation using the necessary formulas at each step.
3. Write a recursive function to determine the position of the permutation at each step.

Calculating the Number of Permutations

When the length of the given number array is n, there are n! (n factorial) permutations. This is the product of all integers from 1 to n.

For example, if the length of the array is 3, the number of permutations is 3! = 6.

Negative Calculation and Recursion for Order Calculation

To calculate the order, we need to consider the cases after a specific number has been selected. For instance, if we assume we choose 1, we recursively call the remaining numbers’ permutations to compute the order.

This approach helps us find out how many permutations are possible for each number and perform the calculations.

Java Code Implementation

Below is the Java code to solve the “Finding the Order of a Permutation” problem:

public class PermutationOrder {
    
    public static void main(String[] args) {
        int[] numbers = {1, 2, 3}; // Given array
        int[] target = {2, 1, 3};   // Target permutation to calculate the order
        int rank = findRank(numbers, target);
        System.out.println("Order of the target permutation: " + rank);
    }
    
    public static int findRank(int[] numbers, int[] target) {
        int n = numbers.length;
        boolean[] used = new boolean[n];
        return getRank(numbers, target, used, 0);
    }
    
    private static int getRank(int[] numbers, int[] target, boolean[] used, int index) {
        int rank = 1; // Default order starts from 1
        int n = numbers.length;
        
        for (int i = 0; i < n; i++) {
            // If the number is smaller than the target number
            if (!used[i]) {
                for (int j = 0; j < target[index]; j++) {
                    if (j == numbers[i]) {
                        break;
                    }
                    rank += factorial(n - index - 1); // Add (n-1)! for each smaller number
                }
            }
            if (target[index] == numbers[i]) {
                used[i] = true; // Use that number
                break;
            }
        }
        
        if (index < n - 1) {
            rank += getRank(numbers, target, used, index + 1); // Recursive call for the next index
        }
        
        return rank;
    }

    private static int factorial(int n) {
        if (n == 0) return 1;
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}
            

This code uses a recursive approach to calculate the order based on the given number array and target permutation. The main function getRank incrementally checks each number in the target permutation and determines the order based on combinations with other numbers.

Example Test Cases

After writing the code, you can validate the results through several examples as follows:

• Input: [1, 2, 3], Target: [2, 1, 3] → Output: 3
• Input: [1, 2, 3], Target: [1, 3, 2] → Output: 2
• Input: [1, 2, 3], Target: [3, 2, 1] → Output: 6

You can iterate as much as needed using various arrays and target permutations with the above code to obtain the correct output. Since various test cases can be generated just from the combinations of permutations, it is essential to evaluate the accuracy and efficiency of the algorithm.

Conclusion

In this article, we addressed the problem of finding the order of permutations using Java. We emphasized how the combination of recursive approaches, the calculation of the number of permutations, and the algorithm for checking the exact order effectively solved the problem. This should enhance the understanding of coding tests and greatly aid in solving a wider range of problems.