C++ coding test course, finding the order of permutations

Hello, everyone! Today, we will take a deep dive into the Finding the Order of Permutations problem, which frequently appears in C++ coding tests. This problem will be very helpful in understanding the concept of permutations and developing combinatorial problem-solving skills. Permutations refer to all possible arrangements of a given set of numbers, and problems utilizing this concept are applied in various fields.

Problem Description

We will explore the concept of permutations and C++ implementation through the process of solving a problem as follows:

Problem: Given integers N and K, find the K-th permutation among all permutations that can be made using the numbers from 1 to N. Assume K starts from 1.

Input Format

  • The first line contains integers N (1 ≤ N ≤ 10) and K (1 ≤ K ≤ N!).

Output Format

Output the K-th permutation on a single line, separated by spaces.

Example

Input:
3 2

Output:
2 1 3

Approach to the Problem

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

  1. Understand the basic concept of permutations.
  2. Design a method to find the K-th permutation when N numbers are given.
  3. Implement the method of generating permutations in code.
  4. Return the K-th permutation.

Method of Generating Permutations

There are various methods for generating permutations; here we will use the method utilizing factorials. The permutations of N numbers yield N! combinations, and the algorithm for generating these combinations helps to efficiently calculate the K-th permutation directly.

Factorial Calculation

The factorial N! is defined as N * (N-1) * (N-2) * … * 1. For example, 3! = 6. Through this, we can calculate the number of possible choices for selecting each number given N.

A Little More Specifically

When listing the numbers from 1 to N, the first number can be chosen based on K. For instance, if K is 2, we find the K-th permutation by considering the number of ways to choose the next number based on each chosen first number.

C++ Code Implementation

Now, let’s write the C++ code based on the above approach. This code will output the K-th permutation using the given N and K.


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Factorial calculation function
long long factorial(int n) {
    if (n == 0) return 1;
    long long result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

// Function to find the K-th permutation
vector<int> getKthPermutation(int n, int k) {
    vector<int> numbers;
    for (int i = 1; i <= n; i++) {
        numbers.push_back(i);
    }
    
    k--; // 0-indexing
    vector<int> permutation;

    for (int i = 0; i < n; i++) {
        long long fact = factorial(n - 1 - i);
        int index = k / fact;
        permutation.push_back(numbers[index]);
        numbers.erase(numbers.begin() + index); // Remove the selected number from the list
        k %= fact;
    }

    return permutation;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> kthPermutation = getKthPermutation(n, k);
    
    for (int num : kthPermutation) {
        cout << num << " ";
    }
    
    return 0;
}

Code Explanation

  1. Factorial Function: Calculates and returns the factorial of the given N.
  2. K-th Permutation Function: Stores numbers from 1 to N in a vector and iterates to find the K-th permutation.
  3. Calculates the number of possible scenarios at each step to decide which number to select.
  4. The selected number is removed from the list, and K is updated for the next number selection.

Testing and Result Verification

In the above code, input N and K, and check if it outputs the K-th permutation correctly. For example, entering N=3 and K=2 should output 2 1 3.

Conclusion

Today, we learned about how to find the order of permutations using C++. This algorithm can enhance understanding of permutations and help solve various algorithmic problems. Since it is a commonly tested type in coding interviews, make sure to practice sufficiently.

Thank you!