Java语言字典序排序算法解析及代码示例-创新互联

字典序法就是按照字典排序的思想逐一产生所有排列。

在数学中，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。 这种泛化主要在于定义有序完全有序集合（通常称为字母表）的元素的序列（通常称为计算机科学中的单词）的总顺序。

对于数字1、2、3......n的排列，不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的。例如对于5个数字的排列 12354和12345，排列12345在前，排列12354在后。按照这样的规定，5个数字的所有的排列中最前面的是12345，最后面的是 54321。

例如，由1,2,3组成的所有排列，从小到大的依次为：

123,132,213,231,312,321
由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.

首先要对给定的字符集中的字符规定了一个先后关系，在此基础上按照顺序依次产生每个排列。

[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。

生成给定全排列的下一个排列，所谓一个的下一个就是这一个与下一个之间没有字典顺序中相邻的字符串。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。

后一个排列与前一个排列之间存在一定的关系，后一个排列的求解过程如下：

设有排列(p)=2763541，按照字典式排序，它的下一个排列是什么？

2763541 （找最后一个正序35）
2763541 （找3后面比3大的最后一个数4）
2764531（交换3,4的位置）
2764135 （把4后面的5,3,1反转）

下面给出求 p[1…n] 的下一个排列的描述：

求 i = max{j | p[j – 1] < p[j]} （找最后一个正序）
求 j = max{k| p[i – 1] < p[k]} （找最后大于 p[i – 1] 的）
交换 p[i – 1] 与 p[j]得到 p[1] … p[i-2] p[j] p[i] p[i+1] … p[j-1] p[i-1] p[j+1] … p[n]
反转 p[j] 后面的数得到 p[1] …p[i-2] p[j] p[n] … p[j+1] p[i-1] p[j-1] … p[i]

代码实现如下：

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;
		}
	}
	//已经到最后一个排列了 全部是逆序
	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;
}