The dictionary order method is to generate all arrangements one by one according to the idea of dictionary sorting.
In mathematics, dictionary or dictionary order (also known as vocabulary order, dictionary order, alphabetical order, or dictionary order) is a method of alphabetical order in which words arranged alphabetical based on alphabetical order. This generalization mainly lies in defining the total order of sequences (often called words in computer science) of elements that define an ordered completely ordered set of elements (often called alphabet).
For the arrangement of numbers 1, 2, 3...n, the sequence of different arrangements is determined by comparing the sequence of corresponding numbers one by one from left to right. For example, for the arrangements 12354 and 12345 of the 5 numbers, the arrangement 12345 is in front and the arrangement 12354 is in the back. According to this regulation, the first one among all the arrangements of the 5 numbers is 12345 and the last one is 54321.
For example, all arrangements composed of 1, 2, 3, from small to large are:
123,132,213,231,312,321
All arrangements consisting of 1, 2, 3, 4:
1234, 1243, 1324, 1342, 1423, 1432,
2134, 2143, 2314, 2341, 2413, 2431,
3124, 3142, 3214, 3241, 3412, 3421,
4123, 4132, 4213, 4231, 4312, 4321.
First, a sequence of characters in the given character set must be specified, and on this basis, each arrangement is generated in sequence.
[Example] Character set {1,2,3}, smaller numbers are first, so the full arrangement generated in dictionary order is: 123, 132, 213, 231, 312, 321.
Generate the next permutation given a full permutation, and the so-called next one is the string adjacent to the next one without dictionary order. This requires that this one has the same prefix as the next one as long as possible, that is, the variation is limited to the shortest possible suffix.
There is a certain relationship between the latter arrangement and the previous arrangement. The solution process of the latter arrangement is as follows:
With arrangement (p)=2763541, sorted by dictionary, what is its next arrangement?
2763541 (Find the last positive order 35)
2763541 (Find the last number 4 after 3 and is larger than 3)
2764531 (switch 3, 4 positions)
2764135 (Invert 5, 3, 1 after 4)
The following is a description of the next arrangement of p[1…n]:
Find i = max{j | p[j 1] < p[j]} (Find the last positive order)
Find j = max{k| p[i 1] < p[k]} (Find the last one greater than p[i 1])
Exchange p[i 1] and p[j] to get p[1] … p[i-2] p[j] p[i] p[i+1] … p[j-1] p[i-1] p[j+1] … p[n]
Reverse the number after p[j] to get p[1] …p[i-2] p[j] p[n] … p[j+1] p[i-1] p[j-1] … p[i]
The code implementation is as follows:
private static int[] getPermutation(int[] in) {int[] ns = in;int base = -1;for (int i=ns.length-1; i>=1; i--) {if (ns[i-1] < ns[i]) {base = i-1;break;}}// It has been arranged to the last one and it is in reverse order if (base == -1) return null;int bigger=0;for (int i=ns.length-1; i>=base; i--) {if (ns[i] > ns[base]) {bigger = i;break;}}// System.out.println(bigger);swap(ns, base, bigger);reverse(ns,base+1,ns.length-1);return ns;}private static void reverse(int[] ns, int i, int j) {int left = i, right = j;while (left < right) {swap(ns, left, right);left++;right--;}}private static void swap(int[] ns, int base, int bigger) {int temp = ns[base];ns[base] = ns[bigger];ns[bigger] = temp;}Summarize
The above is all about the analysis of Java language dictionary sorting algorithm and code examples. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!