第k个排列

题目描述

给定参数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

示例2

输入:

2
2

输出:

21

题解

Python

import itertools

def main():
    def power(n: int) -> int:
        assert n > 0
        p = 1
        for i in range(1, n + 1):
            p *= i
        return p

    # 读取输入
    # 生成所有的排列
    # 找到第k个排列
    n = int(input())
    assert 1 <= n <= 9
    k = int(input())
    power_n = power(n)
    assert 1 <= k <= power_n

    # 生成所有的数字
    nums = tuple(i for i in range(1, n + 1))
    # 生成排列的迭代器
    it = itertools.permutations(nums)
    # 注意, k是从1开始计数的
    for i in range(k):
        ans = next(it)

    # 打印结果
    s = "".join(map(str, ans))
    print(s)

if __name__ == "__main__":
    main()

C++

#include <cassert>

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

void solution() {
  int n = 0;
  std::cin >> n;
  assert(n > 0);
  int k = 0;
  std::cin >> k;
  assert(k > 0);

  std::string line;
  for (int i = 1; i <= n; ++i) {
    line += i + '0';
  }

  int count = 1;
  while (count < k && std::next_permutation(line.begin(), line.end())) {
    count += 1;
  }
  std::cout << line << std::endl;
}

int main() {
  solution();
  return 0;
}