问题描述：
n个元素{1,2，…,n}有n!个不同的排列。将这n!个排列按字
典序排列，并编号为0,1，…,n!-1.每个排列的编号为其字典序值。例如，当
n=3时，6个不同排列的字典序值如下：
字典序值排列 0 1 2 3 4 5
123 132 213 231 312 321
算法设计
给定n及n个元素{1,2，…,n}的一个排列，计算出这个排列的字典
序值，以及按字典排列的下一个排列。
数据输入和数据输出
数据输入：第1行是元素个数n。接下来的1行是n个元素{1,2，…,n}的一个排列。
结果输出：第一行是字典序值，第2行是按字典序排列的下一个排列，如果不存在则输出-1
输入文件示例 输出文件示例
8 8227
2 6 4 5 8 1 7 3 2 6 4 5 8 3 1 7
问题一
本题可以与全排列问题一起思考。本题与全排列问题不同点在于swap函数，也就是交换方式不同。全排列中，如：123，把3放前面来是直接与1换位置，但是字典序里，3是被插进前面去的，并不是换前面去的。全排列的输出为：
123
132
213
231
321
312
发现最后2行没有，与字典序的排序不同，这就是问题所在。
因此我们的swap函数应该为：
private static void Swap2(int[] list, int k, int m) { //将元素还回去
int temp = list[k];
for (int i = k; i < m; i++) {
list[i] = list[i + 1];
}
list[m] = temp;
}
private static void Swap1(int[] list, int k, int m) { //将元素排到最前面
int temp = list[m];
for (int i = m; i > k; i--) {
list[i] = list[i - 1];
}
list[k] = temp;
}这里写了两个swap函数，因为插回去以后，还得还回去，但是2个函数并不通用。
问题二
了解次序的运算规律，这里次序是由逆序数来运算的，我们以3412为例子。逆序数就是指前面的数大于后面的数。
，
3大于后面的1和2，因此3的逆序数为2；4大于后面的1和2，因此4的逆序数也为2；1后面没有比它小的，所以为0；2后面没有数了，因此也为0。所以3412的次序就为，2*3!+2*2! = 12+4=16。（逆序数后面的为该数后面有几位数的阶乘）
我们再举例一个：2341,首先2仅大于后面的1，然后3也仅大于后面的1，4同理。得：1*3!+1*2!+1*1!=6+2+1=9。
通过以上2个例子我相信你已经掌握次序的运算规律了。下面给出根据这些规律写出的代码。
public static long Function(int i, int n, int[] list){
if(i == list.length)
return 0;
return Function(i + 1, n, list) + (order(list[i], list, i + 1) - 1) * factorial(n - i -1);
}
private static long factorial(int n) { //阶乘
long result = 1;
for (int i = 2; i <= n ; i++) {
result *= i;
}
return result;
}
private static int order(int num, int[] list, int start) { //计算逆序数,对于每个元素计算后面有多少元素比它小
int count = 1;
for (int i = start; i < list.length; i++) {
if(list[i] < num)
count++;
}
return count;
}除了这种做法，我们也可以全排列出来，用count记录这是第几个，在每次排列前判断一下，如果符合这种排序就输出count，但是代码效率会偏低。（这里这种方法的代码只需要在我完整代码里perm函数中加个比对就好）
完整代码展示
这里放出完整代码供参考：
package com.chenhao.Demo;
import java.util.Scanner;
public class Dictionary {
public static long Count = 0;
public static long judge = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] list = new int[n];
for (int i = 0; i < list.length; i++) {
list[i] = sc.nextInt();
}
System.out.println("次序为：" + Function(0, n, list));
judge = Function(0, n, list);
for (int i = 0; i < list.length; i++) { //将数组初始化
list[i] = i + 1;
}
perm(list,0, n - 1);
}
public static long Function(int i, int n, int[] list){
if(i == list.length)
return 0;
return Function(i + 1, n, list) + (order(list[i], list, i + 1) - 1) * factorial(n - i -1);
}
private static long factorial(int n) { //阶乘
long result = 1;
for (int i = 2; i <= n ; i++) {
result *= i;
}
return result;
}
private static int order(int num, int[] list, int start) { //计算逆序数,对于每个元素计算后面有多少元素比它小
int count = 1;
for (int i = start; i < list.length; i++) {
if(list[i] < num)
count++;
}
return count;
}
public static void perm(int[] list, int k, int m){ //产生list[k:m]的所有排列
if(k == m ){
if (Count == judge + 1) {
for (int i = 0; i <= m; i++) {
System.out.print(i == m ? list[m] : list[i] + " ");
}
System.out.println();
}
Count++;
}else {
for (int i = k; i <= m ; i++) {
Swap1(list, k, i);
perm(list, k + 1, m);
Swap2(list, k, i);
}
}
}
private static void Swap2(int[] list, int k, int m) { //将元素还回去
int temp = list[k];
for (int i = k; i < m; i++) {
list[i] = list[i + 1];
}
list[m] = temp;
}
private static void Swap1(int[] list, int k, int m) { //将元素排到最前面
int temp = list[m];
for (int i = m; i > k; i--) {
list[i] = list[i - 1];
}
list[k] = temp;
}
}