Kotlin coding test course, Finding the Order of Permutations

Hello! Today we will learn how to determine the order of permutations using Kotlin. Solving algorithm problems is an important part of coding tests, and understanding permutations and combinations will help solve various problems.

Problem Description

This problem is to find the order of a specific permutation from the second index to the first index of a given sequence. The elements of the sequence consist of integers from 1 to N, and there are no duplicates. For example, when the sequence is [1, 2, 3], all permutations are as follows:

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

In the above example, [2, 1, 3] is the 3rd permutation. The goal is to output the order number in this manner.

Input Format

N (1 ≤ N ≤ 20)
P (N integers, unique numbers from 1 to N)

Output Format

Print the order of the given permutation P.

Problem Solving

To solve this problem, we can proceed with the following steps:

1. Generate all possible permutations.
2. Find the given permutation in the generated list.
3. Print the index of that permutation (starting from 1).

Kotlin Implementation

Now, let’s write the code. First, we will use Kotlin’s permutations function to generate all permutations and then find the index of the input permutation.

import kotlin.math.*

fun  List.permutations(): List> {
    if (isEmpty()) return listOf(emptyList())
    val result = mutableListOf>()
    for (i in indices) {
        val item = this[i]
        val remaining = this.filterIndexed { index, _ -> index != i }
        for (permutation in remaining.permutations()) {
            result.add(listOf(item) + permutation)
        }
    }
    return result
}

fun main() {
    val n = 3
    val sequence = listOf(2, 1, 3)

    val totalNumbers = (1..n).toList()
    val allPermutations = totalNumbers.permutations()

    val index = allPermutations.indexOf(sequence) + 1 // Add 1 since the index starts at 0
    println("The permutation $sequence is the ${index}th order.")
}

Code Explanation

The main parts of the code above are as follows:

• The permutations function recursively generates and returns all permutations as a list.
• The main function defines N and the given permutation, and calls permutations to generate all possible permutations.
• Finally, it uses indexOf to find and print the index of the given permutation.

Performance Considerations

When N is 20, the number of possible permutations corresponds to 20!. This is about 240 million cases. Therefore, when N reaches 20, there can be issues with memory and execution speed, so for large inputs, it is necessary to consider other approaches (e.g., the mathematical properties of permutations). Nonetheless, this method works well for smaller numbers.

Conclusion

In this tutorial, we learned how to determine the order of permutations. We showed the process of solving the problem using Kotlin’s features and explained various considerations to aid understanding of algorithm problems. Let’s continue to tackle more algorithm problems and learn various approaches!