{"id":33414,"date":"2024-11-01T09:16:17","date_gmt":"2024-11-01T09:16:17","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33414"},"modified":"2024-11-01T11:38:48","modified_gmt":"2024-11-01T11:38:48","slug":"java-coding-test-course-finding-the-order-of-permutations","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33414\/","title":{"rendered":"Java Coding Test Course, Finding the Order of Permutations"},"content":{"rendered":"<\/p>\n\n\n
This article aims to address the commonly asked problem of “Finding the Order of a Permutation” in coding tests using Java. We will detail the necessary theories, approaches, and code examples required to solve this problem.<\/p>\n<\/header>\n\n
Problem Definition<\/h2>\n
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]<\/code>, all permutations are listed as follows:<\/p>\n
\n
1, 2, 3<\/li>\n
1, 3, 2<\/li>\n
2, 1, 3<\/li>\n
2, 3, 1<\/li>\n
3, 1, 2<\/li>\n
3, 2, 1<\/li>\n<\/ul>\n
For example, for the number 2<\/code>, when the permutation is 2, 1, 3<\/code>, 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.<\/p>\n<\/section>\n\n
Problem Approach<\/h2>\n
To solve this problem, you can follow these steps:<\/p>\n
\n
Calculate the total number of permutations based on the length of the given array.<\/li>\n
Calculate the position based on the target permutation using the necessary formulas at each step.<\/li>\n
Write a recursive function to determine the position of the permutation at each step.<\/li>\n<\/ol>\n<\/section>\n\n
Calculating the Number of Permutations<\/h2>\n
When the length of the given number array is n<\/code>, there are n!<\/code> (n factorial) permutations. This is the product of all integers from 1 to n<\/code>.<\/p>\n
For example, if the length of the array is 3, the number of permutations is 3! = 6<\/code>.<\/p>\n<\/section>\n\n
Negative Calculation and Recursion for Order Calculation<\/h2>\n
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<\/code>, we recursively call the remaining numbers’ permutations to compute the order.<\/p>\n
This approach helps us find out how many permutations are possible for each number and perform the calculations.<\/p>\n<\/section>\n\n
Java Code Implementation<\/h2>\n
Below is the Java code to solve the “Finding the Order of a Permutation” problem:<\/p>\n
\npublic class PermutationOrder {\n \n public static void main(String[] args) {\n int[] numbers = {1, 2, 3}; \/\/ Given array\n int[] target = {2, 1, 3}; \/\/ Target permutation to calculate the order\n int rank = findRank(numbers, target);\n System.out.println(\"Order of the target permutation: \" + rank);\n }\n \n public static int findRank(int[] numbers, int[] target) {\n int n = numbers.length;\n boolean[] used = new boolean[n];\n return getRank(numbers, target, used, 0);\n }\n \n private static int getRank(int[] numbers, int[] target, boolean[] used, int index) {\n int rank = 1; \/\/ Default order starts from 1\n int n = numbers.length;\n \n for (int i = 0; i < n; i++) {\n \/\/ If the number is smaller than the target number\n if (!used[i]) {\n for (int j = 0; j < target[index]; j++) {\n if (j == numbers[i]) {\n break;\n }\n rank += factorial(n - index - 1); \/\/ Add (n-1)! for each smaller number\n }\n }\n if (target[index] == numbers[i]) {\n used[i] = true; \/\/ Use that number\n break;\n }\n }\n \n if (index < n - 1) {\n rank += getRank(numbers, target, used, index + 1); \/\/ Recursive call for the next index\n }\n \n return rank;\n }\n\n private static int factorial(int n) {\n if (n == 0) return 1;\n int result = 1;\n for (int i = 1; i <= n; i++) {\n result *= i;\n }\n return result;\n }\n}\n <\/code><\/pre>\n
This code uses a recursive approach to calculate the order based on the given number array and target permutation. The main function getRank<\/code> incrementally checks each number in the target permutation and determines the order based on combinations with other numbers.<\/p>\n<\/section>\n\n
Example Test Cases<\/h2>\n
After writing the code, you can validate the results through several examples as follows:<\/p>\n
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.<\/p>\n<\/section>\n\n
Conclusion<\/h2>\n
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.<\/p>\n<\/section>\n