第k个排列

题目描述

给定参数 n，从 1到 n会有n个整数:1,2,3…,n，这n个数字共有 n! 种排列。按大小顺序升序列出所有排列的情况，并一一标记，当n=3时，所有排列如下:

。“123

“132”

。“213”

“231”

。“312”

“321”

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

输入描述

输入两行:

第一行为 n，给定n的范围是[1，9]

第二行为 k，给定k的范围是 [1，n!]

输出描述

输出排在第k 位置的数字

示例1

输入

3

3

输出

213

说明

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

示例2

输入

2

2

输出

21

说明

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

题解

康托展开

源码

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

public class KNumber {

	static Input input ;
	static {
		input = new Input("3\n" +
				"3");
		input = new Input("5\n" +
				"96");
	}

	static  String[] numbers = new String[]{"1","2","3","4","5","6","7","8","9"};
	static  int n = 0;
	static  int k = 0;
	/*
	康托展开的逆运算
	既然康托展开是一个双射，那么一定可以通过康托展开值求出原排列，即可以求出n的全排列中第x大排列。

	如n=5,x=96时：

	首先用96-1得到95，说明x之前有95个排列.(将此数本身减去1)
	用95去除4! 得到3余23，说明有3个数比第1位小，所以第一位是4.
	用23去除3! 得到3余5，说明有3个数比第2位小，所以是4，但是4已出现过，因此是5.
	用5去除2!得到2余1，类似地，这一位是3.
	用1去除1!得到1余0，这一位是2.
	最后一位只能是1.
	所以这个数是45321.
	 */
	public static void main(String[] args) {
		n = Integer.parseInt(input.nextLine()) ;
		k = Integer.parseInt(input.nextLine());
		List<Integer> list = new ArrayList<>();
		
		
		int div = 1;
		for (int i = 1; i < n; i++) {
			div *= i;// 计算阶乘数
			list.add(i); // 填充使用到的数字
		}
		list.add(n);

		int x = k - 1;
		String result = "";
		for (int i = n-1; i > 0; i--) {
			// 计算阶乘数
			int num = x / div;
			x = x % div;
			div /= i;
			result += list.get(num); // 获取该位置上的数字
			list.remove(num); // 数字使用过后不允许再次使用
		}
		result += list.get(0);
		System.out.println(result);
	}

}