算法创作|蓝桥杯——排列序数问题解决方法

问题描述示例：如果用a b c d这4个字母组成一个串，有4!=24种，如果把它们排个序，每个串都对应一个序号：abcd  0abdc  1acbd  2acdb  3adbc  4adcb  5bacd  6badc  7bcad  8bcda  9bdac  10bdca  11cabd  12cadb  13cbad  14cbda  15cdab  16cdba  17...现在有不多于10个两两不同的小写字母，给出它们组成的串，求出该串在所有排列中的序号吗？输入：一行，一个串输出：一行，一个整数，表示该串在其字母所有排列生成的串中的序号。注意：最小的序号是0。解决方案严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。注意：不要使用package语句。注意：主类的名字必须是：Main还是全排，模拟它排序的过程，n最大是10，而10！不会超时，交换的全排不是字典序，标记数组的全排是字典序import java.util.Arrays;import java.util.Scanner;public class 排列序数 {public  static void main(String[] args) {Scanner  in = new Scanner(System.in);a  = in.next();ch1  = a.toCharArray();Arrays.sort(ch1);n  = ch1.length;vis  = new boolean[n];ch2  = new char[n];dfs(0);System.out.println(ans);}static  char[] ch1;static  char[] ch2;static  boolean[] vis;static  int n;static  String a;static  int cnt=0,ans=0;static  void dfs(int m) {if(ans>0)return;if(m>=n)  {//                      System.out.println(new  String(ch2));if(a.equals(new  String(ch2)))ans  = cnt;cnt++;return;}for(int  i=0;i<n;i++)if(!vis[i])  {vis[i]  = true;ch2[m]  = ch1[i];dfs(m+1);vis[i]  = false;}}//     static  void swap(int i,int j) {//             char  c = ch[i];//             ch[i]  = ch[j];//             ch[j]  = c;//     }}结语在查阅了大量资料后，我们小组决定借鉴蓝桥杯比赛——排列序数问题，在查阅资料的基础上加上了一些我们自己对于排列的思考，也借鉴了一些参考答案，最终完成这一问题。在本次作业过程中，我们都意识到了自己python基础的不足，原本是想自己创作一个问题并解决，但由于基础较差，所以只能从网上搜寻了题目和资料来完成。在接下来的时间里，我们小组决定将基础夯实，争取在本学期结束时能够独立创作出题目以及解决方案。主编：欧洋作者：罗梦思、曾希明、陈柯桦