A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:012 021 102 120 201 210What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
// 以下为验证方法,通过查找,显示1234的全排列
for (int i = 1; i <= 24; i++) {
System.out.println(find(4, i));
}
} /**
* @param length
* 总长度
* @param position
* 位置,第一个:1,第二个:2
* @return 全排列第N个位置的数。
*/
private static String find(int length, int position) {
List<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < length; list.add(i++))
;
int[] f = new int[length];
int[] x = new int[length];
f[length - 1] = 1;
for (int i = 2; i <= length; i++) {
f[length - i] = f[length - i + 1] * i;
}
int n = position - 1;
for (int i = 0; i < length - 1; i++) {
while (n >= f[i + 1] && x[i] < length - i - 1) {
n -= f[i + 1];
x[i]++;
}
} StringBuilder buff = new StringBuilder(length);
for (int i = 0; i < length; i++) {
buff.append(list.remove(x[i]));
}
return buff.toString();
}
也就是说第一位如果是1,那么他至少是排在(N-1)!+1以后了
比如10!=3628800,超过100w,那么第一位只能是0,0被用掉
第二位,9!=362880,可以放2×3628800=7257600,也就是第二位是第二种可能(不一定是2,而是排除前面已经用掉的数字侯,排名第二小的数字)。1000000-725760=274240,8!=40320,40320×6=241920,第三位就是“第6个”,以此类推
public class Test{
static int jc(int n){
if(n==0)return 1;
else return n*jc(n-1);
}
public static void main(String args[]) {
/*a[]可以改成char型,26个字母均可,按字母顺序输入*/
int a[]={0,1,2,3,4,5,6,7,8,9};
int b[]=new int[a.length];
/*number是要查询的序列号*/
int number=1000000;
int num=number-1;
int flag=-1;
for(int i=1;i<=a.length;i++){
if(jc(i)>num){
flag=a.length-i;
break;
}
}
if(flag==-1){
System.out.println("wrong num ");
System.exit(0);
}
for(int i=0;i<flag;i++){
b[i]=a[i];
}
int aa[]=new int[a.length-flag];
for(int i=0;i<aa.length;i++){
aa[i]=a[flag+i];
}
while(flag<a.length){
int n=a.length-flag-1;
int m=num/jc(n);
if(m==n+1){
for(int i=0;i<aa.length;i++){
b[i+flag]=aa[aa.length-i-1];
}
flag=a.length;
}
if(m<n+1){
b[flag]=aa[m];
for(int i=m;i<aa.length-1;i++){
aa[i]=aa[i+1];
}
num=num-m*jc(n);
flag++;
}
}
for(int i=0;i<b.length;i++){
System.out.print(b[i]);
}
}
}
新手没用过几个java类,悲催啊
第二位,9!=362880,可以放2×3628800=7257600,也就是第二位是第二种可能(不一定是2,而是排除前面已经用掉的数字侯,排名第二小的数字)。