Java dictionary sorting algorithm analysis and code examples

Lexicographical ordering is the idea of lexicographical ordering to produce all permutations one by one.

In mathematics, a dictionary or lexicographical order (also known as lexical order, lexicographical order, alphabetical order, or lexicographical order) is an alphabetical order of words based on alphabetical order. This generalization is primarily concerned with the overall order of the sequences (often called words in computer science) that define the elements of an ordered and completely ordered set (often called an alphabet).

For the numbers 1, 2, 3... The order of n is determined by comparing the sequence of corresponding numbers from left to right. For example, for the five digits 12354 and 12345, 12345 comes first and 12354 comes last. According to this rule, the first of all the permutations of the five numbers is 12345, and the last is 54321.

For example, all the permutations composed of 1,2 and 3, from smallest to largest, are:

123,132,213,231,312,321
All permutations of 1,2,3 and 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 of characters in a given character set is defined, and then each sequence is generated sequentially.

[example] character set {1,2,3}, smaller numbers come first, so the full arrangement generated in lexicographical order is :123,132,213,231,312,321.

To generate the next permutation for a given full permutation, the next permutation for a given full permutation is a string that is not contiguous in the lexicographic order between the first and the next. This requires that the first and the next have the longest common prefix possible, meaning that the variation is limited to the shortest suffix possible.

There is a definite relation between the latter permutation and the former, and the solution process of the latter permutation is as follows:

Given that p =2763541, in lexicographic order, what is the next arrangement?

2763541 (find the last positive 35)
2763541 (find the last number after 3 that is greater than 3, 4)
2764531 (swap 3,4)
2764135 (reverse 5,3,1 after 4)

A description of the next permutation of p[1... n] is given below:

i = max{j | p[j w1] < p[j]} (find the last positive order)
j = max{k| p[i 1] < p[k]} (last bigger than p[i 1])
Exchange p[i 1] and p[j] for p[1]... p[ES75en-2] p[j] p[i] p[i+1]... p p [j - 1] [i - 1] p [j + 1]... p[n]
Reverse the number after p[j] to p[1]... p p [i - 2] [j] p [n]... p p [j + 1] [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;
		}
	}
	// At the end of the day 1 An arrangement   It's all inversions 
	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;
}

conclusion

That's the end of this article on Java dictionary sorting algorithm analysis and code examples, I hope to help you. Interested friends can continue to refer to other related topics in this site, if there is any deficiency, welcome to comment out. Thank you for your support!