题面描述

给定参数$n$，从$1$到$n$会有$n$个整数:$1, 2, 3......n$。这$n$个数字共有$n!$种排列。我们需要按大小顺序升序列出所有排列的情况，并一一标记。给定$n$和$k$，返回第$k$个排列。

解题思路

1. 排列生成的性质：

   • 任何$n$的排列都可以通过固定某个数字，剩余的数字再进行全排列来生成。
   • 比如，对于$n = 3$，固定数字$1$，则其余$2$的排列为$2,3$。

2. 排列数量：

   • 每个数字固定后，其余$n-1$个数字的排列数为$(n-1)!$。
   • 因此，我们可以根据$k$的值判断第一个数字应该是哪个，从而逐步缩小范围。

3. 具体步骤：

   • 计算$(n-1)!$。
   • 根据$k$找到对应的第一个数字。
   • 从可用的数字中移除已选的数字，继续对剩下的数字进行同样的操作，直到所有数字都被选择。

代码分析

1. factorial 函数：

   • 递归计算给定数字$n$的阶乘。

2. getPermutation 函数：

   • 初始化一个可选数字的数组 numbers，包含$1$到$n$的所有整数。
   • 通过循环确定每一个数字的位置，直到构建出完整的排列字符串。
   • 在每一步中，根据当前$k$的值和当前剩余数字的排列数量，确定下一个数字，并从 numbers 中移除该数字。

3. 主函数：

   • 读取输入，调用 getPermutation 函数并输出结果。

cpp

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 计算阶乘
int factorial(int n) {
    return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
}

string getPermutation(int n, int k) {
    vector<int> numbers;
    // 初始化可选数字
    for (int i = 1; i <= n; i++) {
        numbers.push_back(i);
    }

    string permutation = "";
    k--; // k 从 1 开始计数，转为 0 开始计数

    // 逐步构建排列
    for (int i = 0; i < n; i++) {
        int fact = factorial(n - 1 - i); // 计算 (n-i-1)!
        int index = k / fact; // 找到当前数字的索引
        permutation += to_string(numbers[index]); // 添加到结果中
        numbers.erase(numbers.begin() + index); // 移除已选数字
        k %= fact; // 更新 k
    }

    return permutation;
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << getPermutation(n, k) << endl;
    return 0;
}

python

def factorial(n):
    if n == 1 or n == 0:
        return 1
    return factorial(n - 1) * n

def get_permutation(n, k):
    numbers = list(range(1, n + 1))  # 初始化可选数字
    permutation = ""
    k -= 1  # k 从 1 开始计数，转为 0 开始计数

    # 逐步构建排列
    for i in range(n):
        fact = factorial(n - 1 - i)  # 计算 (n-i-1)!
        index = k // fact  # 找到当前数字的索引
        permutation += str(numbers[index])  # 添加到结果中
        numbers.pop(index)  # 移除已选数字
        k %= fact  # 更新 k

    return permutation

if __name__ == "__main__":
    n = int(input())
    k = int(input())
    print(get_permutation(n, k))

java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Permutation {
    
    // 计算阶乘
    public static int factorial(int n) {
        if (n == 1 || n == 0) {
            return 1;
        }
        return factorial(n - 1) * n;
    }

    // 获取第 k 个排列
    public static String getPermutation(int n, int k) {
        List<Integer> numbers = new ArrayList<>();
        // 初始化可选数字
        for (int i = 1; i <= n; i++) {
            numbers.add(i);
        }

        StringBuilder permutation = new StringBuilder();
        k--; // k 从 1 开始计数，转为 0 开始计数

        // 逐步构建排列
        for (int i = 0; i < n; i++) {
            int fact = factorial(n - 1 - i); // 计算 (n-i-1)!
            int index = k / fact; // 找到当前数字的索引
            permutation.append(numbers.get(index)); // 添加到结果中
            numbers.remove(index); // 移除已选数字
            k %= fact; // 更新 k
        }

        return permutation.toString();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        System.out.println(getPermutation(n, k));
        scanner.close();
    }
}

题目内容

给定参数 $n$，从 $1$ 到 $n$ 会有 $n$ 个整数：$1,2,3,…,n$, 这 $n$ 个数字共有 $n!$ 种排列。

按大小顺序升序列出所有排列的情况，并一一标记，当 n = 3 时,所有排列如下:

• “123”
• “132”
• “213”
• “231”
• “312”
• “321”

给定 $n$ 和 $k$，返回第 $k$ 个排列。

输入描述

输入两行，第一行为 $n$，第二行为 $k$，

给定 $n$ 的范围是$[1, 9]$, 给定 $k$ 的范围是$[1, n!]$。

输出描述

输出排在第 $k$ 位置的数字。

样例1

输入

3
3

输出

213

说明

$3$的排列有$123,132,213,…$，那么第三位置就是$213$

样例2

输入

2
2

输出

21

说明

$2$的排列有$12,21$，那么第二位置的为$21$。