如果用a b c d这4个字母组成一个串，有4!=24种，如果把它们排个序，每个串都对应一个序号：
abcd 0
abdc 1
acbd 2
acdb 3
adbc 4
adcb 5
bacd 6
badc 7
bcad 8
bcda 9
bdac 10
bdca 11
cabd 12
cadb 13
cbad 14
cbda 15
cdab 16
cdba 17
…
现在有不多于10个两两不同的小写字母，给出它们组成的串，你能求出该串在所有排列中的序号吗？
【输入格式】
一行，一个串。
【输出格式】
一行，一个整数，表示该串在其字母所有排列生成的串中的序号。注意：最小的序号是0。
例如：
输入：
bdca
程序应该输出：
11
6 10 11
再例如：
输入：
cedab
48ca 54cb 60cd 66ce -> 66cea 68ceb 70ced ->
72d...
程序应该输出：
70
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
在2018年校赛的时候看到这题，那时候什么都没学，有点思路但是没有实现，现在快省sai'le
思路:看到这里肯定是使用回溯算法了，只是怎么使用的问题。这里中间掺杂了!的计算，我们要从开头到结尾枚举字符串字符，以及当前字符串所有排列组合。
每次操作我们只需要看第一个开头的元素，比如a，b，c和d组成的组合，那么加入输入的是bcad，第一个是b，而四个字符组成的组合数是4！= 24，每个字母间隔24/4 = 6 ， a开头从0开始，b开头从6开始，c开头从12开始，d开头从18开始。得到b是6之后，我们开始计算b下面的cad字符串，三个字符组成的组合数是3！= 6，每个字母间隔6/3 = 2 ， c开头是2 + 6 = 8， 再去计算ab字符串，得到答案是8。
n的字符串的序号可以通过n-1的字符串序号累加得出，使用回溯去解决。
值得注意的是，我们在判断cba的时候，我们怎么可以快速得出c在a，b和c中排第几呢，如果是eba呢？我们可以把他们的ascii值存到ArrayList里面并且排序，就可以得到第一个字符在总字符中的排名了，然后再去乘每个字符之间的组合间隔。用错了排序方法可能会浪费很多时间哦，本人就用了一天。
package com.company;
import com.sun.org.apache.xerces.internal.impl.io.ASCIIReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
public class Main {
static private int result;
public static void main(String[] args) {
// write your code here
Scanner scanner = new Scanner(System.in);
String string = scanner.nextLine();
Jump(0,string);
System.out.println(result);
}
static public void Jump(int index,String string){
if (index==string.length()){
//遍历到底了
return;
}
char firstopt = string.charAt(index);
//剩余长度
int length = string.length()-index;
//当前长度的总排列数,即length! = length*(length-1)*(length-2)...
int order = 1;
for (int i = length; i > 0; i--) {
//根据剩余长度 求出当前组合可以得出的排列数
order *= i;
}
char[] chars = string.toCharArray();
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = index; i < chars.length; i++) {
arrayList.add(Integer.valueOf(chars[i]));
}
Collections.sort(arrayList);
得到当前的字母的offset，并乘以字符间的排列间隔得出答案
int offset = arrayList.indexOf(Integer.valueOf(firstopt));
result += offset*order/length;
Jump(index+1,string);
}
}
