最近在准备蓝桥杯，所以今天想对全排列的一些解法进行总结，这样也方便于以后的复习。
<font size="6px">样例问题</font>
这里我选择了一个较为容易理解的题目进行全排列的总结。题目是输入一个字符串，例如"abcd",通过全排列得出该字符串中字符的所有组合方式。
<font size="6px">
一、迭代法</font>
思路分析：这题使用的是迭代法，我的思路是首先创建一个old_list来存储上一次循环中保存的所有字符串。然后对old_list进行初始化，将字符串的0号位添加到old_list中，这其实也相当于完成了第一次循环，将第一次循环得到的所有字符串添加到old_list中。之后从1号位对字符串x进行遍历，取出i号位上的值赋值给临时变量temp并创建一个new_list来存放当次循环得到的字符串。这里必须要创建一个new_list来存放当次循环得到的字符串，不能直接存入到old_list，这样的话会造成重复。然后就是循环遍历old_list中的字符串，对于上一次循环得到的字符串，当次循环的字符总共有三种插入方式，分别是：1、在字符串的前面加上字符 2、在字符串的末尾加上字符 3、在字符串的中间加上字符。当遍历结束后，将new_list赋值给old_list，这样便于下一次循环。最后输出结果。
在这里插入图片描述
public static void main(String[] args) {
String x = "abcd";
全排列总结 a = new 全排列总结();
ArrayList<String> sort1 = a.sort1(x);
System.out.println(sort1.size());
System.out.println(sort1);
}
//迭代法
public static ArrayList<String> sort1(String x) {
ArrayList<String> old_list = new ArrayList<>(); //创建一个List，用来存放上一次循环完成后的字符串
old_list.add(x.charAt(0) + ""); //初始化，将0号位的字符存入list
for (int i = 1; i < x.length(); i++) { //从一号位开始遍历字符串
String temp = x.charAt(i) + "";
ArrayList<String> new_list = new ArrayList<>(); //创建新的list来存放新一轮的字符串
for (String old : old_list) { //循环遍历old_list,取出所有字符串
new_list.add(temp + old); //第一种情况，在字符串的前面加上字符
new_list.add(old + temp); //第二种情况，在字符串的末尾加上字符
for (int j = 1; j < old.length(); j++) {
new_list.add(old.substring(0, j) + temp + old.charAt(j)); //第三种情况，在字符串的中间加上字符
}
}
old_list = new_list; //将new_list中的字符串存给old_list,开始下一次循环
}
return old_list; //返回结果
}
<font size="6px">
二、递归法</font>
思路分析：这题使用的是递归法,是迭代法的改编版。因为是递归法，所以肯定要将一部分的事情交给现在做，另一部分交给递归去完成。所以我们可以先将字符串x的0~n-1号位上的字符排列出所有情况，然后再将n号位上的字符插入到所有情况中，这样就完成了 全排列。如下面代码所示。先创建一个old_list来存放第n个字符插入后的所有情况。然后调用递归，获取0~n-1位上字符串的所有排列情况。然后将第n号位上的字符插入进去即可。插入方法有三种情况，同迭代法是一样的。最后返回结果
public static void main(String[] args) {
String x = "abcd";
全排列总结 a = new 全排列总结();
ArrayList<String> arr = new ArrayList<>();
ArrayList<String> sort2 = a.sort2( x, x.length()-1, arr);
System.out.println(sort2.size());
System.out.println(sort2);
}
// 递归法
public ArrayList<String> sort2(String x, int n, ArrayList<String> arr) {
if (n == 0) { //为递归设置出口
arr.add(x.charAt(0) + ""); //初始化list
return arr;
}
ArrayList<String> old_list = new ArrayList<>(); //为n号位字符创建一个list
ArrayList<String> new_list = sort2(x, n - 1, arr); //调用递归，得到1~n-1号位已经排列好全部情况的list
for (String old : new_list) { // 循环遍历new_list,将字符串n号位的字符插入到全部情况中
old_list.add(x.charAt(n) + old); // 第一种情况，在字符串的前面加上字符
old_list.add(old + x.charAt(n)); // 第二种情况，在字符串的末尾加上字符
for (int j = 1; j < old.length(); j++) {
old_list.add(old.substring(0, j) + x.charAt(n) + old.charAt(j)); // 第三种情况，在字符串的中间加上字符
}
}
return old_list; //返回结果
}
<font size="6px">
三、交换法</font>
思路分析：这题使用的是交换法，运用了回溯的思想。首先是将字符串转换为字符数组，并排列。然后调用sort3方法，每次都循环遍历从k号位到字符串末尾的每一个字符。swap（arr，k，i）意味将第i号位上的的值，交换到第k号位。然后递归调用，直到当k==arr.length时就将排列好的arr添加到全局变量res中，完成一次排列。这里调用完之后必须swap（arr，i，k）将数组复原，然后进行下一次循环。最后得到结果
在这里插入图片描述
public static void main(String[] args) {
String x = "abcd";
全排列总结 a = new 全排列总结();
char[] array = a.toArray(x);
ArrayList<String> sort3 = a.sort3(array, 0);
System.out.println(sort3.size());
System.out.println(sort3);
}
// 交换法
public char[] toArray(String x) { //将字符串转换为字符数组
char[] arr = x.toCharArray();
Arrays.sort(arr);
return arr;
}
ArrayList<String> res = new ArrayList<>(); //定义一个全局变量来存放所有排列情况
public ArrayList<String> sort3(char[] arr, int k) {
if (k == arr.length) {
res.add(new String(arr));
}
for (int i = k; i < arr.length; i++) { //每次都循环遍历每一个未被遍历过的数
swap(arr, k, i); //将第i号位上的值和k号位上的值交换
sort3(arr, k + 1); //从k+1号位开始调用递归，知道遍历完所有数
swap(arr, i, k); //回溯，将字符串复原
}
return res;
}
public void swap(char[] arr, int k, int i) { //交换位置
char temp = arr[k];
arr[k] = arr[i];
arr[i] = temp;
}
<font size="6px">
四、前缀法</font>
思路分析：这题使用的是前缀法，我为本题加了一个条件(字符串必须有序)，在全排列中，按照顺序排列，并且输出第num个排列好的数。Main方法调用sort4（），进入for循环，每次都遍历数组全部，然后遇到if语句，判断数组中某字符的出现次数如果大于在字符串中出现的次数，那说明需要把字符添加到prefix中。最后当字符串prefix的长度等于数组的长度时，即一次排列完成，总数加一。当cnt==num时则输出结果。
public static void main(String[] args) {
String x = "abcd";
全排列总结 a = new 全排列总结();
a.sort4("",x.toCharArray());
}
int cnt=0; //总数
final int num=3; //需要获得第几个的值
//前缀法
public void sort4(String prefix,char[] arr) {
if(prefix.length()==arr.length) { //递归出口
cnt++;
if(cnt==num) { //当字符串prefix的长度等于数组的长度时
System.out.println(prefix); //输出结果
System.exit(0);;
}
}
for(int i=0;i<arr.length;i++) { //每次都遍历数组全部元素
char ch=arr[i];
if(count(prefix.toCharArray(),ch)<count(arr,ch)) { //判断数组中某字符的出现次数如果大于在字符串中出现的次数
sort4(prefix+ch,arr);
}
}
}
public int count(char[] arr,char ch) { //判断字符在数组中出现的次数
int count=0;
for(int i=0;i<arr.length;i++) {
if(arr[i]==ch) {
count++;
}
}
return count;
}
网友评论