我排第几个

描述

现在有"abcdefghijkl”12个字符，将其所有的排列中按字典序排列，给出任意一种排列，说出这个排列在所有的排列中是第几小的？

 

输入

第一行有一个整数n（0<n<=10000）;

随后有n行，每行是一个排列；

输出

输出一个整数m，占一行，m表示排列是第几位；

样例输入

3

abcdefghijkl

hgebkflacdji

gfkedhjblcia

样例输出

1

302715242

260726926

方法一：

public static int getSortNum(String value) { // 记录已经出现过得字符和未出现的字符顺序 String sort = "abcdefghijkl"; // 记录结果数 int res = 1; for(int i=0;i<value.length();i++) { // 依次取各位的字符 char c = value.charAt(i); // 查看该字符在所有字符中的当前顺序 int head = sort.lastIndexOf(c); // 计算排在前面的字符串数量 res += ((head-i)*factorial(11-i)); // 修改字符顺序，将当前出现的字符，交换到字符最前面 // 因为我们不关心已经出现过得字符的顺序，我们只要知道出现过哪些字符以及未出现的字符的字典序 // 所以直接把出现过得字符扔到最前面就可以了 sort = change(sort, head); } return res; } /** * 求阶乘 * @param i * @return */ public static int factorial(int i) { if(i==0) return 0; int result = 1; for(;i>1;i--) { result *= i; } return result; } /** * 将字符串第a位换到最前面 * @param str * @param a * @param b * @return */ public static String change(String str,int a) { char[] chars = str.toCharArray(); char temp = chars[a]; for(int i=a;i>0;i--) { chars[i] = chars[i-1]; } chars[0] = temp; return String.valueOf(chars); } 方法二：

static Scanner scan=new Scanner(System.in); public static void main(String[] args){ //这个是对的，只是耗时特别长，但让考试时这样写肯定得不了分。 Test08_2 test8=new Test08_2(); int a=scan.nextInt(); while(a>0){ test8.start(); a--; } } public void start(){ //这个是对的，只是耗时特别长，但让考试时这样写肯定得不了分。 String a=scan.next(); String b="abcde"; char[] c=b.toCharArray(); sort(c,0,a); sum=0; a2=0; } int sum=0; int a2=0; public void sort(char[] a,int b,String d){ if(a2==-1){ return; } if(b==a.length-1){ sum++; String c=String.valueOf(a); if(c.equals(d)){ a2=-1; System.out.println(sum); } return; } for(int i=b;i<a.length;i++){ char temp=a[i]; a[i]=a[b]; a[b]=temp; if(b<a.length-2){ String b1=String.valueOf(a); String b2=b1.substring(b+1, a.length); char[] b3=b2.toCharArray(); Arrays.sort(b3); String b5=""; for(int i1=0;i1<b+1;i1++){ b5+=a[i1]; } String b4=b5+""+String.valueOf(b3); a=b4.toCharArray(); } sort(a,b+1,d); temp=a[i]; a[i]=a[b]; a[b]=temp; } }方法三：

public class Test08_3 { public static long postion (int n){ if(n==1){ return 1; } return n*postion(n-1); } public static long index(char[] p,char c,int inde){ int size=1; for (int i = 0; i < inde; i++) { if(c-p[i]>0){ size++; } } return (c-96)-size; } public static long getSize(char[] p,int index,long size){ char c=p[index]; if(index==p.length-1){ return 1; } long num=index(p, c, index)*postion(12-index-1); return num+getSize(p, ++index, num); } public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); sc.nextLine(); for (int i = 0; i < n; i++) { String str=sc.nextLine(); char [] cc=str.toCharArray(); System.out.println(getSize(cc, 0, 0)); } }