An algorithmic proposition: given a string S[0…N-1], design an algorithm to enumerate the full arrangement of S. For example: 123, the full arrangement is: 123,132,213,231,312,321
I am just ignorant. It took me a day and a half to finally sort out the dictionary. I can’t see the code written by the master. There are still many optimizations in my code. I will record it first. Recursion is still a bit confusing now.
java code: recursive implementation (considering repeated characters)
Take the string 1234 as an example:
1 – 234
2 – 134
3 – 214
4 – 231
How to ensure no omissions: Before each recursion, ensure that the order of 1234 remains unchanged.
1 package stringtest;
2 import java.util.ArrayList;
3 import java.util.Collections;
4
5 /**Title description
6 Enter a string and print out all the permutations of characters in the string in dictionary order.
7 For example, if the string abc is input, all strings abc, acb, bac, bca, cab, and cba that can be arranged by the characters a, b, and c will be printed.
8 Enter a description:
9 Enter a string whose length does not exceed 9 (characters may be repeated). The characters include only uppercase and lowercase letters.
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);
twenty three }
twenty four }
25
26/**
27 * Idea: Use the idea of recursion. to fulfill
28 * Let a be the first one: arrange the remaining bcd in full
29 * Let b first: the remaining acd are fully arranged
30 * Let c come first: arrange the remaining abc in full order
31 * Let d come first: arrange the remaining abc in full order
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 //Recursive exit condition
46 if(array.length<1){
47 return;
48 }
49 //If start and end are not equal, it means a sorting is completed
50 if(start==end){
51 String val = new String(array);
52 //Here we also determine the duplication of elements (method 1)
53 if (!list.contains(val))
54 list.add(val);
55 }else{
56 //Backtracking method, fix one element at the front each time, and arrange all subsequent elements
57 for (int i = start; i <= end; i + + ) {
58
59 //Consider the case of repeated elements (method 2)
60 boolean flag = true;
61 for (int j = start; j < i; j + + ) {
62 if(array[j] == array[i]){<!-- -->//You can also replace i with end here
63 flag = false;
64}
65 }
66
67 //If there are duplicate elements, skip the large loop and compare next
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 code: dictionary order (considering repeated characters)
Fully permuted non-recursive algorithm: Organized into algorithm language? Steps: back search, small and large, exchange, flip–
? Find after: the last ascending position i in the string, that is, S[k]>S[k + 1](k>i), S[i]
? Exchange: Si, Sj;
? Flip: S[i + 1…N-1]
Personal summary: Take 926520 as an example
①: Search the string from back to front, find the first value in descending order, which is 2, and the position is 1
②: Then find the minimum value of 2 and the following number larger than 2, which is 5 (Supplement: Find the first value larger than 2 from right to left, which is 5.)
③: Exchange positions of 2 and the found 5
④: Flip all the numbers after 2
Finally done:
The first step: sort the strings first
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 //First sort the array from small to large
12 Arrays.sort(arr);
13 fullArray(arr,0,arr.length-1);
14}
15
16/**
17 * This method is to fully arrange the string
18*
19 * @param arr
20 * @param i
21 * @param j
twenty two */
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 //①: Search from back to front to find the first value in descending order
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 //Indicates that the order has been sorted, and there is no descending value.
37 return false;
38 }
39 }
40 // System.out.println("The first descending value n: " + arr[first] + ", first subscript: " + first);
41 //②: Find the number after first that is greater than 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 //The minimum value of a number larger than 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("The minimum value m larger than n: " + arr[min] + ", min subscript: " + min);
56 //③: Then exchange the positions of min and first
57 swap(arr,min,first);
58 //④: Because the positions have been exchanged, the current min is the previous first, and all the strings after min are reversed.
59 // System.out.println("Before flipping the numbers after n:" + String.valueOf(arr));
60 resver(arr,first + 1,end);
61 // System.out.println("After flipping the numbers after n:" + String.valueOf(arr));
62 }
63}
64
65 //Realize the flipping from the s position to the end position of the arr array
66 private static void resver(char[] arr, int start, int end) {
67 while(start<end){
68 //You can assign the last value to the previous one
69 char temp1 = arr[start];
70 arr[start + + ] = arr[end];
71 arr[end--] = temp1;
72 }
73}
74
75 //Exchange positions between elements
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}