排列的字典序问题(java版)
排列的字典序问题(java版) 【排列的字典序问题(java版)】
文章图片
文章图片
import java.io.*;
import java.util.Scanner;
//字典序
/*
* 思路：
①如何得到2 6 4 5 8 1 7 3的下一个排列？
* 1 从尾部往前找第一个P(i-1) < P(i)的位置
* 2 6 4 4 5 8 1 <-- 7 <-- 3
* 最终找到1是第一个变小的数字，记录下1的位置i-1
* 2 从尾部往前找到第一个大于1的数
* 2 6 4 4 5 8 1 7 3 <--
* 最终找到3的位置，记录位置为m
* 3 交换位置i-1和m的值
* 2 6 4 4 5 8 3 7 1
* 4 倒序i位置后的所有数据
* 2 6 4 4 5 8 3 1 7
②如何得到2 6 4 5 8 1 7 3所对应的字典序值
* 比2小的数有1个，则 value+=1*7！；* 比6小的数有4个，则 value+=4*6！；* 比4小的数有2个，则 value+=2*5！；* 比5小的数有2个，则 value+=2*4！；* 比8小的数有3个，则 value+=3*3！；* 比1小的数有0个，则 value+=0*2！；* 比7小的数有1个，则 value+=1*1！；* 比3小的数没有；* */
class lab1_2_4 {
public static void main(String[] args) throws IOException {
Scanner input = new Scanner(System.in);
//int n = input.nextInt();
//int n = 8;
File outFile = new File("F://input1.2.4.txt");
//要现在F盘建文件
BufferedReader br = new BufferedReader(new FileReader(outFile));
String str1 = br.readLine();
int n = Integer.parseInt(str1.trim());
String str = br.readLine();
//读取文件的数据
String[] arrs = str.split(" ");
int[] arr = new int[n];
for(int i = 0;
i < arrs.length;
i++){
arr[i] = Integer.parseInt(arrs[i]);
}
String data1 = "",data2 = "\n";
System.out.println("orderValue:" + orderValue(arr,n));
data1 += orderValue(arr,n);
int[] b = nextNumber(arr,n);
//System.out.print("nextNumber: ");
for (int x:b
) {
//System.out.print(x +" ");
data2 += x + " ";
}
File inFile =new File("F://output1.2.4.txt");
//算出的数据存在F盘
Writer out =new FileWriter(inFile);
out.write(data1);
//把数据存进文件
out.write(data2);
//把数据存进文件
out.close();
}
public static int fi(int n){//计算阶乘方法
if(n == 0 || n == 1){
return 1;
}
else
return n * fi(n-1);
}
public static int orderValue(int[]a,int n){//用二重循环计算出数组中的数字所代表的值
int value = https://www.it610.com/article/0;
for( int i = 0;
i < a.length;
i++){
int sum = 0;
//记录每次比a[i]小的数的个数
for(int j = i;
j < a.length;
j++){
if(a[i]>a[j]){
sum ++;
}
}
value += sum * fi(n - i -1);
}
return value;
}
public static int[] nextNumber(int[] a, int n){
int index1 = 0;
//从右端开始降序的索引
int index2 = 0 ;
for( int i = n-1;
i >= 1;
i --){
if(a[i] > a[i - 1]){
index1 = i - 1;
break;
}
}
for( int i = n-1;
i >= index1;
i --){
if(a[i] > a[index1]){
index2 = i;
break;
}
}
swap(a,index1,index2);
arrayReverse(a,index1 + 1);
return a;
}
public static void arrayReverse (int[] arr, int x){//逆序数组
for(int start=x,end=arr.length-1;
start<=end;
start++,end--){
int tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
}
}
public static void swap(int[] arr,int index1,int index2){//把数组中的两个元素交换
int tem ;
tem = arr[index1] ;
arr[index1] = arr[index2];
arr[index2] = tem;
}}
/*
* 心得：
* 我觉这个题，尤其是求解字典序值的时候有点像是冒泡排序那种感觉，
* 两重循环，上一层循环的起点 看作是下一层的起点
* 之前总是编译不通过是因为没有用break语句，经过调试发现是那里出现了问题
* */
推荐阅读
- 热闹中的孤独
- JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
- 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
- 一个人的旅行，三亚
- 布丽吉特，人生绝对的赢家
- 慢慢的美丽
- 尽力
- 一个小故事，我的思考。
- 家乡的那条小河
- 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量