算法创作|蓝桥杯——排列序数问题解决方法
问题描述
示例：如果用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。
解决方案
严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意：不要使用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基础的不足，原本是想自己创作一个问题并解决，但由于基础较差，所以只能从网上搜寻了题目和资料来完成。在接下来的时间里，我们小组决定将基础夯实，争取在本学期结束时能够独立创作出题目以及解决方案。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-03-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读