排列序数 （Java代码）无需生成全排列

解题思路:
本来是想生成所有全排列，然后从里面找的，但是发现容易超时，那么有没有方法可以不用生成全排列，直接观察所给的排列就能知道它在所有排列中占的位置呢？有。

比如说，bdca这个排列。

①先看首字母b,不用说，它前面肯定还有a***，有3！= 6种情况，即dbca前面还有至少6个排列。

②再看第二个字母d,d前面还有a,b,c三个字母,但是b在第一位已经用过了，所以排在d前面的排列还有ba**,bc**，各有2!种情况,即dbca前面还有至少6+2×2！= 10个排列。

③再看第三个字母c,c前面还有a,b两个字母，但是b已经用过了,所以前面还有bda*这种组合，但是因为一共4个字母，有3个字母被确定，剩下的一个字母也就是确定的了，即bda*就是bdac这1种情况，即dbca前面还有至少10+1 = 11个排列。

④到了第四个字母a,因为一共就4个字母，而此时前3个字母都已经确定了，所以第四个字母也就确定了，dbca前面不会还有新的排列。

⑤所以，最后得到dbca前面有11个排列,从0开始排的话，dbca就被排到了11的位置

类似地，大家可以类比一下n个字母的情况，留给大家思考的空间。
注意事项:

参考代码:

import java.util.Scanner;

public class T1815{
        //i表示第i个字母(从0起),n表示暂未确定字母的长度
	public static int f(String s,int i,int n) {
		if(n == 1) return 0;
		int ans = 0,cnt = 0;
		//统计第i个字母前有多少字母被占用
		for(int j = 0;j<i;j++)
			if(s.charAt(i)>s.charAt(j))
				cnt++;
		ans = (s.charAt(i) - 'a'-cnt)*factor(n-1) + f(s,i+1,n-1);
		return ans;
	}
	//求阶乘
	public static int factor(int n) {
		if(n == 1 || n == 0) return 1;
		else 
			return n*factor(n-1);
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()) {
			String s = in.next();
			System.out.println(f(s,0,s.length()));
		}
		in.close();
	}
}