思路
先根据给定排列计算出对应数字num,然后加上m,再算出num+m对应的排列,
由于从0开始计算比较方便,我这里记录是从0开始的,第0个就表示第一个,
思路用到的是做全排列做多了就能理解的一种规律,计算过程我暂且理解为进制转换的变形,
写几个例子方便理解
先是根据排列算出对应数字
比如123,从左往右开始算,
- 1属于剩余排列[1,2,3]的第0个,0 * 2!
- 2属于剩余排列[2,3]的第0个, 0 * 1!
- 3属于剩余排列[3]的第0个,0 * 0!
- 那么123就是全排列中的第(0 * 2! + 0 * 1! + 0 * 0! = 0) 个
比如312
- 3属于剩余排列[1,2,3]的第2个,2 * 2!
- 1属于剩余排列[1,2]的第0个, 0 * 1!
- 2属于剩余排列[2]的第0个,0 * 0!
- 那么312就是全排列中的第(2 * 2! + 0 * 1! + 0 * 0! = 4) 个
根据数字算出对应排列,当然是反着来了
比如算[1,2,3]全排列中的第5个(这个5是从0开始算的,其实对应的就是321)
- 5 / 2! = 2, 对应剩余排列[1,2,3]中的3,取余数5 % 2! = 1
- 1 / 1! = 1, 对应剩余排列[1,2]中的2,取余数1 % 1! = 0
- 0 / 0! = 0, 对应剩余排列[1]中的1,
- 结束,答案就出来了,就是321,没错吧
java 代码
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
BigInteger[] factorial = new BigInteger[n + 1];
factorial[0] = new BigInteger("1");
for (int i = 1; i <= n; i++)
factorial[i] = factorial[i - 1].multiply(new BigInteger(String.valueOf(i)));
ArrayList<Integer> list = new ArrayList<>();
for (int i = 1; i <= n; i++) list.add(i);
BigInteger num = new BigInteger("0");
for (int i = 0; i < n; i++) {
int c = list.indexOf(a[i]);
list.remove(c);
num = num.add(new BigInteger(String.valueOf(c)).multiply(factorial[list.size()]));
}
for (int i = 1; i <= n; i++) list.add(i);
num = num.add(new BigInteger(String.valueOf(m)));
for (int i = 0; i < n; i++) {
BigInteger k = num.divide(factorial[n - i - 1]);
a[i] = list.get(k.intValue());
num = num.mod(factorial[n - i - 1]);
list.remove(k.intValue());
}
for (int i = 0; i < n; i++) {
bw.write(a[i] + " ");
}
bw.flush();
bw.close();
}
}
这规律真妙