字典序排列算法解析
字典序全排列算法分析：
给定⼀组字符串s,⾸先将字符串转化为字符数组c，将字符数组c中的元素从⼩到⼤排序，得到的即为字典序全排列的第⼀个排列。
因为每个字符的⼤⼩是按照他的Ascii码对应的数字⽐较⼤⼩的，所以这⾥以⼀串数字为例。例如：15432.其实可以将字典序全排列看作数字进位的过程，例如：从后往前数，倒数第四位的数达到了最⼤值（即从后往前找，后⾯的数总是⼩于或等于前⾯的数，满⾜从尾部向前递增过程 ），则倒数第五位需要进位（即第五位不满⾜从尾部向前递增过程）， 所以从第后4位找最⼩的⼤于1的数，即2。将2 和1 完成调换，倒数第五位完成进位， 然后将后四位转为最⼩的数（即从⼩到⼤排列)位1345。所以15432的下⼀个排列为21345.总结步骤如下：1、寻找下⼀个排列的步骤：
1.从尾部向前找第⼀个变⼩的位置i-1，此时p(i-1)<p(i）。
2.从i位置向后找，找到最⼩的⼤于p(i-1)的值，记该位置为m，即p(m)> p(i-1),p(m+1)<p(i-1). //因为这些数刚好满⾜从尾部向前是从⼩到⼤，所以可从后向前找第⼀个⼤于p(i-1)的数的位置即为所求。
3.交换位置i-1和位置m处的值。 //相当于完成进位。
感动作文800字
4，将从位置i到结尾的所有数据从⼩到⼤排列。//组合为从位置i到结尾能构成的最⼩的数。因为从i到结尾此时还是满⾜从⼤到⼩，所以只需要⼀个反转操作即可。
2、寻找下⼀个排列的代码：
private static boolean nextPermutate(char[] data) {
int end = data.length - 1;
int swapPoint1 = end, swapPoint2 = end;
// the actual swap-point is swapPoint1 - 1
while (swapPoint1 > 0 && data[swapPoint1] <= data[swapPoint1 - 1])//从尾部向前找到第⼀个变⼩的数
swapPoint1--;
if (swapPoint1 == 0)
return fal;
el {
while (swapPoint2 > 0 && data[swapPoint2] <= data[swapPoint1 - 1])//从尾部到swapPoint1找到第⼀个⼤于swapPoint1-1的位置
swapPoint2--;
swap(data, swapPoint1 - 1, swapPoint2);
rever(data, swapPoint1, end);//⽤的是反转的操作，但其实起到的作⽤是从⼩到⼤排序。
return true;
}
}朋友新年祝福语
private static void swap(char[] data, int left, int right) { //调换顺序
char temp = data[left];
data[left] = data[right];
data[right] = temp;
}
private static void rever(char[] data, int left, int right) {
马锐拉for (int i = left, j = right; i < j; i++, j--)
swap(data, i, j);
}
3、全排列代码
写好了寻找下⼀个排列的代码，下⼀步就可写字典序全排列的代码了。只要循环调⽤就可以了，即：只要存在下⼀个全排列，则调⽤⼀次寻找下⼀个全排列。代码如下：
public static void Prim(char[] data) {
Arrays.sort(data);
do{
System.out.println(data);
纸尿裤保质期几年}while(nextPermutate(data)//data 下⼀个排列);
}
以上代码是将全排列依次打印，也可以按需要改为接收全排列，代码如下：
public static void Prim(char[] data,char[][] q) {//传⼊⼀个⼆维数组q接收全排列
Arrays.sort(data);
int i =0;
do{
for(int j = 0; j< data.length; j++){
q[i][j] = data[j];
}
i++;
}while(nextPermutate(data));
}
因为要传⼊⼀个⼆维数组q⽤来接收全排列列表，所以要对其⼤⼩定义。
int len = s.length(); //s为传⼊的字符串
int l = factorial(len); //总排列数
char [][] q = new char [l][len];
CharArray(),q);//将字符串s转为字符数组，获取其字典序全排列结果
public static int factorial(int n){
int sun = 1;
for(int i=1; i<= n; i++){
sun = sun * i;
}
return sun;
}
4.寻找谜底
public static void main(String[] args) { //接收输⼊
Scanner sc = new Scanner(System.in);
int n = 0;
if(sc.hasNext()){
n = sc.nextInt();
}
String rv[] = new String[n];
for(int i = 0; i < n; i++){
rv[i] = sc.next();
}
for(int i = 0; i < n; i++){
羊肉面的做法
miDi(rv[i]);
}
}
public static void miDi(String s){ //输出s 的谜底
int len = s.length();
int l = factorial(len); //总排列数
char [][] q = new char [l][len];深圳市行政区划
CharArray(),q);//字典序全排列结果
int indexB = (indexA(CharArray()) + len)%l; //谜底
System.out.println(q[indexB]);
普通话考试查分
}
public static int indexA(char[][]q, char[] d){
for(int i = 0; i < q.length; i++){
if(charCompare(q[i], d)){
return i;
}
}
二次元可爱头像
return -1;
}
public static boolean charCompare(char[] a, char[] b){ for(int j = 0; j < a.length; j++){
if (a[j] != b[j]){
return fal;
}
}
return true;
}
