The title
Enter a string and print out all permutations of the characters in the string in lexicographical order. For example, if you enter the string ABC, you print out all the strings ABC, ACb, BAC, BCA, CAB, and CBA that can be arranged by characters A, B, and C. Note: characters may duplicate! For example, all permutations of Aab are aab, ABA, baA
parsing
Preliminary knowledge
Full permutation: a permutation of N numbers in a certain order. It means that all elements participate in the arrangement. These permutations are n factorial. . Because the first position can put N elements, when the first position is determined, the second position can put n-1 elements, and so on, after the current n-1 position is determined, the last position can only put 1, so the total number of permutations is n*(n-1)… *1=n! .
Thinking a
Let’s start with the case where we don’t repeat, because it’s a little bit easier, so let’s start with simplicity. Output all lexicographic permutations for a given string. We can do it in the same way as DFS, specifically using the definition of full permutation. To ensure lexicographical order, sort the given string first so that the first string is the smallest. For example, 213, all the permutations are: 123, 132, 213, 231, 312, 321. The idea is to start with the highest position, each position is evaluated from 1,2, and 3 respectively. As long as the highest position takes the minimum value of the current remaining element first, the generated string is guaranteed to be the same as the last one. To keep track of the values taken in each round, add an access array that records which elements have been accessed and whose index corresponds to the sorted string index. The simple process is as follows:
- The first position is iterated from 1,2,3, and the second position is iterated from 1,2, and 3, but it is found that 1 has already been iterated. To ensure the minimum, the second position is iterated from 1,2, and 3. The third position is also iterated from 1,2, and 2 have been accessed
- The third position has no elements to traverse, so go back to the previous layer, the second position is 3, the third position is found to have been accessed,2 is not accessed, so take 3, then form 1,3,2.
- There are no elements left to iterate through in the second position, so we go back to the first position, and the process is similar from there.
It is also easy to handle duplicate elements. If there are duplicate elements, it will only result in duplicate permutations.
/** * full array with repeating characters * use set to duplicate *@param str
* @return* /
public static ArrayList<String> Permutation(String str) {
ArrayList<String> result = new ArrayList<>();
if(str == null || str.equals("")) {
return result;
}
char[] chars = str.toCharArray();
Arrays.sort(chars);
Set<String> set = new LinkedHashSet<>();
boolean[] vis = new boolean[chars.length];
char[] temp = new char[chars.length];
permutation(0, temp, chars, set, vis);
result.addAll(set);
return result;
}
/** * DFS traversal character array * uses access array to determine if elements at a certain location have been accessed *@param index
* @param temp
* @param chars
* @param set
* @param vis
*/
public static void permutation(int index, char[] temp, char[] chars, Set<String> set, boolean[] vis) {
if(index == chars.length) {
set.add(new String(temp));
return;
}
for(int i = 0; i < chars.length; i++) {
if(! vis[i]) { temp[index] = chars[i]; vis[i] =true;
permutation(index + 1, temp, chars, set, vis);
vis[i] = false; }}}Copy the codeIdea 2
Another way to think about it is to decompose the subproblem, you can divide the permutation problem into fixed first position, the rest of the elements permutation problem. Then do the same for the rest of the elements, fix the first position, the rest of the elements are arranged. As shown in figure:
public static ArrayList<String> Permutation2(String str) {
ArrayList<String> result = new ArrayList<>();
if(str == null || str.equals("")) {
return result;
}
char[] chars = str.toCharArray();
Set<String> set = new TreeSet<>();
permutation2(0, chars, set);
result.addAll(set);
return result;
}
public static void permutation2(int index, char[] chars, Set<String> set) {
if(index == chars.length - 1) {
set.add(new String(chars));
return;
}
for(int i = index; i < chars.length; i++) {
swap(chars, index, i);
permutation2(index + 1, chars, set); swap(chars, index, i); }}public static void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
Copy the codeThe second traceback above is just to restore the original state of the parent problem when traceback, so that the parent problem continues to swap elements with the next location, starting a new child problem.
Thought three
Idea two, can we optimize it so that we don’t have redundant permutations. The first idea might be to not swap if the elements in the first part are equal. For example, abb, the first position can be swapped with the second and third positions respectively, because they are not the same as A, resulting in ABB, BAB, bbA. When you look at the second position, for bab, the second position will be swapped with the third position to get BBA. And BBA has already appeared in the process of swapping with the first position. So you can’t just look at whether the interchange elements are equal or not. We find that the reason for the occurrence of repetition is that b has already appeared in the first position, and the same elements cannot be exchanged to this position, that is, there cannot be repeated elements as the first part of the arrangement problem, which will definitely lead to the occurrence of repeated sub-problems. So for each position traversal, we add a set to record the elements that have been present at that position. This allows you to separate sets, but since there is no guarantee of lexicographical order, you still end up sorting the result set once.
/ / -- -- -- -- -- -- -- -- -- -- -- -- -- -- method 3
public static ArrayList<String> Permutation3(String str) {
ArrayList<String> result = new ArrayList<>();
if(str ! =null && str.length() > 0) {
permutation3(0, str.toCharArray(), result);
Collections.sort(result);
}
return result;
}
public static void permutation3(int index, char[] chars, ArrayList<String> result) {
if(index == chars.length - 1) {
result.add(new String(chars));
return;
}
// Record the elements that already appear at that location
Set<Character> characters = new HashSet<>();
for(int i = index; i < chars.length; i++) {
if(! (i ! = index && characters.contains(chars[i]))) { characters.add(chars[i]); swap(chars, index, i); permutation3(index +1, chars, result); swap(chars, index, i); }}}public static void swap(char[] chars, int i, int j) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
Copy the codeThinking four
Idea four is the famous lexicographical algorithm ah. The algorithm is based on the idea of reverse order. The number of inversions is the number of pairs of such combinations in a sequence. For a sequence 12345, we know that the higher the position of the inversion, the further back the position of the sequence, and the larger the lexicographical order. For example, 12534, the reverse sequence is generated in the third position; 51234, the reverse position is generated in the first position of the highest bit, so it is greater than 12534. Conclusion: The higher the inversion position is, the more the inversion pairs are, and the farther the inversion position is, 54321 is the maximum. The lexicographical algorithm is as follows:
- Find the first positive pair in the current sequence from back to front, and record the position A of the positive pair.
- Find the first element greater than that position from back up and record that position B.
- Swap elements in two positions
- Change to positive order for all elements of A+1.
Why do we need to find the first positive pair?
To find the next permutation of the current permutation is to add an inversion pair, or move the inversion position higher. After we find the positive-order position, it indicates that the position is the previous position of the current reverse order. So if we just create an inversion at that position, it will be larger than the original permutation.
Why do I have to go back and find the first element that is greater than the positive order?
Because in order to be only larger than the original arrangement, it is only necessary to produce the smallest inversion, which is just larger than the number in the positive position. So why is it that the first one is greater than, when we were looking for the first positive pair, all the positions we walked through were in reverse order, so the first one is greater than which is just greater than, and then everything is greater than position A.
Why do we finally want to restore the original inverse interval to positive order?
Because we have moved the reverse order higher, keeping the rest of the order minimal ensures that the new order is only larger than the original one.
//----------- method four lexicographical algorithm ---------
public static ArrayList<String> Permutation4(String str) {
ArrayList<String> result = new ArrayList<>();
if(str ! =null && str.length() > 0) {
char[] chars = str.toCharArray();
Arrays.sort(chars);
result.add(new String(chars));
while(true) {
int firstPositiveOrder = chars.length - 2;
while(firstPositiveOrder >= 0
&& chars[firstPositiveOrder] >= chars[firstPositiveOrder + 1]) {
firstPositiveOrder--;
}
if(firstPositiveOrder == -1) {
break;
}
int index = chars.length - 1;
while(chars[index] <= chars[firstPositiveOrder]) {
index--;
}
swap(chars, firstPositiveOrder, index);
reverse(chars, firstPositiveOrder + 1, chars.length);
result.add(newString(chars)); }}return result;
}
public static void reverse(char[] chars, int begin, int end) {
for (int i = begin, j = end - 1; i < j; i++, j--) { swap(chars, i, j); }}Copy the codeconclusion
The idea of full permutation can be used to solve the problem of multiple characters in a certain order.