排列的字典序问题

最新推荐文章于 2021-04-09 15:24:33 发布

轩辕泳

最新推荐文章于 2021-04-09 15:24:33 发布

阅读量1.1k

点赞数

分类专栏：算法设计 java 文章标签：字典序排列

本文链接：https://blog.csdn.net/chris_paul3/article/details/13300495

版权

java 同时被 2 个专栏收录

26 篇文章

订阅专栏

算法设计

14 篇文章

订阅专栏

问题描述：n个元素{1,2,……, n }有n!个不同的排列。将这n!个排列按字典序排列，并编号为0，1，…，n!-1。每个排列的编号为其字典序值。例如，当n=3时，6 个不同排列的字典序值如下：给定n以及n个元素{1,2,……, n }的一个排列，计算出这个排列的字典序值，以及按字典序排列的下一个排列。

思路：

/**

* 算法思路：从左往右起对大于当前位置的数进行减一运算，
* 然后将当前位置的数乘以后边位数的阶乘。
*
* */
public class DicOrder {

/**
* @param args
*/
public static void main(String[] args) {
Deal d=new Deal();
Scanner sc=new Scanner(System.in);
System.out.println("请输入长度");
int n=sc.nextInt();
int [] f=new int[n];
int [] arr=new int[n];
for(int i=0;i<n;i++){
arr[i]=sc.nextInt();
}
d.Fac(f);
int num=0;
for(int i=0,k=arr.length-1;i<arr.length;i++,k--){
if(k==0){
System.out.println(num);
}else{
num+=(arr[i]-1)*f[k];
d.moreNum(i, arr);
}
}
}

}
class Deal{
/**
* 用于计算出后边用到的阶乘
* @param arr
*/
void Fac(int arr[]){
for(int i=0;i<arr.length;i++){
if(i==0) {
arr[i]=1;
}else{
arr[i]=arr[i-1]*i;
}
}
}

void moreNum(int n,int arr[]){
for(int i=n+1;i<arr.length;i++){
if(arr[n]<arr[i]){
arr[i]--;
}
}
}
}