Java language dictionary sorting algorithm analysis and code example

Dictionary ordering is to produce all permutations one by one according to the idea of dictionary sorting.

In mathematics, dictionary or dictionary order (also known as lexical order, dictionary order, alphabetical order or dictionary order) is a method of arranging words alphabetically based on alphabetical order. This generalization mainly lies in defining the total order of the sequence of elements (commonly known as words in Computer Science) of an ordered and completely ordered set (commonly known as the alphabet).

For numbers 1, 2, 3 The order of n is determined by comparing the corresponding numbers one by one from left to right. For example, for the five digit permutations 12354 and 12345, the permutation 12345 is in the front and the permutation 12354 is in the back. According to this provision, the top of all the arrangements of the five numbers is 12345 and the bottom is 54321.

For example, all permutations composed of 1, 2 and 3 are as follows from small to large:

123132213231321 all permutations consisting of 1,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 of all, a sequence relationship shall be specified for the characters in a given character set, and on this basis, each arrangement shall be generated in order.

[example] for the character set {1,3}, the smaller number comes first, so the full arrangement generated in dictionary order is: 123321.

Generate the next permutation of a given full permutation. The so-called next of a permutation is that there is no adjacent string in the dictionary order between this one and the next. This requires that this one and the next have a common prefix as long as possible, that is, the change is limited to the suffix as short as possible.

There is a certain relationship between the latter arrangement and the former arrangement. The solution process of the latter arrangement is as follows:

There is a permutation (P) = 2763541. According to the dictionary sort, what is its next permutation?

2763541 (find the last positive order 35) 2763541 (find the last number 4 greater than 3 after 3) 2764531 (exchange the positions of 3 and 4) 2764135 (reverse 5 and 1 after 4)

The next permutation of P [1... N] is described below:

Find I = max {J | P [J C 1] < p [J]} (find the last positive order) find J = max {K | P [I C 1] < p [k]} (find the last greater than p [I C 1]) exchange P [I C 1] and P [J] to get P [1]... P [I-2] P [J] P [i] P [i + 1]... P [J-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:

summary

The above is all about the analysis of Java language dictionary sorting algorithm and code examples in this paper. I hope it will be helpful to you. Interested friends can continue to refer to other related topics on this site. If there are deficiencies, please leave a message to point out. Thank you for your support!