全排列算法(递归和字典)
一个算法命题:给定字符串S[0…N-1],设计算法,枚举S的全排列。如:123,全排列就是:123,132,213,231,312,321
java代码:递归实现(考虑有重复的字符)
以字符串1234为例:
1 – 234
2 – 134
3 – 214
4 – 231
如何保证不遗漏: 每次递归前,保证1234的顺序不变。
1 package stringtest;
2 import java.util.ArrayList;
3 import java.util.Collections;
4
5 /**题目描述
6 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
7 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
8 输入描述:
9 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
10 *
11 *
12 * @author Administrator
13 *
14 */
15 public class FullArray {
16
17 public static void main(String[] args) {
18 FullArray fa = new FullArray();
19 String str = "abc";
20 ArrayList<String> arrayList = fa.Permutation(str);
21 for (String string : arrayList) {
22 System.out.println(string);
23 }
24 }
25
26 /**
27 * 思路:利用递归的思想。来实现
28 * 先让a第一位:剩余bcd做全排列
29 * 先让b第一位:剩余acd做全排列
30 * 先让c第一位:剩余abc做全排列
31 * 先让d第一位:剩余abc做全排列
32 *
33 * @param str
34 * @return
35 */
36 ArrayList<String> list = new ArrayList<>();
37 public ArrayList<String> Permutation(String str) {
38 char[] array = str.toCharArray();
39 permutaionTest(array,0,str.length()-1);
40 Collections.sort(list);
41 return list;
42 }
43
44 public void permutaionTest(char[] array,int start,int end){
45 //递归退出条件
46 if(array.length<1){
47 return;
48 }
49 //如果start和end不相等,说明完成一次排序
50 if(start==end){
51 String val = new String(array);
52 //这里也是判断元素重复情况(方式一)
53 if (!list.contains(val))
54 list.add(val);
55 }else{
56 //回溯法,每次固定一个元素在最前面,后面元素进行全排列
57 for (int i = start; i <= end; i++) {
58
59 //考虑有重复元素的情况(方式二)
60 boolean flag = true;
61 for (int j = start; j < i; j++) {
62 if(array[j] == array[i]){//这里吧i换成end也行
63 flag = false;
64 }
65 }
66
67 //有重复元素就跳过大循环,下一个比较
68 if(flag){
69 swap(array,start,i);
70 permutaionTest(array,start+1,end);
71 swap(array,i,start);
72 }
73 }
74 }
75 }
76
77 private void swap(char[] array, int start, int i) {
78 if(start!=i){
79 char tmp = array[start];
80 array[start] = array[i];
81 array[i] = tmp;
82 }
83 }
84 }
java代码:字典序排列(考虑有重复的字符)
全排列的非递归算法:整理成算法语 步骤:后找、小大、交换、翻转——
后找:字符串中最后一个升序的位置i,即S[k]>S[k+1](k>i),S[i]<S[i+1];
查找(小大):S[i+1…N-1]中比Ai大的最小值
交换:Si,Sj;
翻转:S[i+1…N-1]
个人总结:以926520为例
①:字符串从后往前找,找到第一个降序的值为2,位置为1
②:然后找出2和后面比2大的数的最小值为5
③:2和找出的5进行位置交换
④:把2后面所有的数进行翻转
最后大功告成:
第一步:先把字符串进行全排序
1 package com.qyzx.string;
2
3 import java.util.ArrayList;
4 import java.util.Arrays;
5
6 public class AllArray2 {
7
8 public static void main(String[] args) {
9 String str = "1212";
10 char[] arr = str.toCharArray();
11 //先对数组进行重小到大进行排序
12 Arrays.sort(arr);
13 fullArray(arr,0,arr.length-1);
14 }
15
16 /**
17 * 该方法是对字符串进行全排列
18 *
19 * @param arr
20 * @param i
21 * @param j
22 */
23 private static boolean fullArray(char[] arr, int start, int end) {
24 if(end<1){
25 return true;
26 }
27 while(true){
28 System.out.println(arr);
29 //①:从后往前找,找出第一个降序的值
30 int first = end;
31 for (int i = end; i >= 1; i--) {
32 if(arr[i-1]<arr[i]){
33 first = i-1;
34 break;
35 }else if(i==1){
36 //说明已经排好序了,没有降序的值。
37 return false;
38 }
39 }
40 // System.out.println("第一个降序的值n:"+arr[first]+",first下标:"+first);
41 //②:找出first后面比first大的数
42 ArrayList<Integer> list = new ArrayList<>();
43 for (int i = first+1; i < end+1; i++) {
44 if(arr[first]<arr[i]){
45 list.add(i);
46 }
47 }
48 //比first大的数的最小值
49 int min = list.get(0);
50 for (int i = 1; i < list.size(); i++) {
51 if(arr[min]>arr[list.get(i)]){
52 min = list.get(i);
53 }
54 }
55 // System.out.println("比n大的最小值m:"+arr[min]+",min下标:"+min);
56 //③:然后交换min和first的位置
57 swap(arr,min,first);
58 //④:因为交换了位置,所以现在的min就是之前的first,把min后面所有的字符串进行反转
59 // System.out.println("n后面数字进行翻转前:"+String.valueOf(arr));
60 resver(arr,first+1,end);
61 // System.out.println("n后面数字进行翻转后:"+String.valueOf(arr));
62 }
63 }
64
65 //实现arr数组的s位置到end位置的翻转
66 private static void resver(char[] arr, int start, int end) {
67 while(start<end){
68 //可以把最后赋值给前面
69 char temp1 = arr[start];
70 arr[start++] = arr[end];
71 arr[end--] = temp1;
72 }
73 }
74
75 //进行元素之间交换位置
76 public static void swap(char[] arr,int from ,int to){
77 char s = arr[from];
78 arr[from] = arr[to];
79 arr[to] = s;
80 }
81
82 }
个人愚昧,搞了一天半,才终于把字典排列搞出来,看不到大神写的代码,我的代码还有很多优化之处,先记录下,递归现在还是有点蒙。