蓝桥杯-排列序数

• 题目
  标题：排列序数

  如果用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

再例如：
输入：
cedab
程序应该输出：
70

• 代码

import java.util.Scanner;

public class Permution {

    static int[] mem = new int[12];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int sum = 0 ;
        int len = str.length();
        char[] c = str.toCharArray();
        int[] cnt = new int[len];
        for(int i=0;i<len-1;i++) {
            //计算之后有几位比当前位小
            for(int j=i+1;j<len;j++) {
                if(c[j]<c[i])
                    cnt[i]++;
            }
            sum += cnt[i] * f(len-i-1);
        }
        System.out.println(sum);
    }
    //计算N的阶乘（N>0）
    static int f(int n) {
        if(n==1)
            mem[1] = 1;
        return mem[n]==0 ? mem[n] = f(n-1)*n : mem[n];
    }
}

• 结果

abdefgc
33