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

在數學中，字典或詞典順序（也稱為詞匯順序，字典順序，字母順序或詞典順序）是基于字母順序排列的單詞按字母順序排列的方法。 這種泛化主要在于定義有序完全有序集合（通常稱為字母表）的元素的序列（通常稱為計算機科學中的單詞）的總順序。

對于數字1、2、3......n的排列，不同排列的先后關系是從左到右逐個比較對應的數字的先后來決定的。例如對于5個數字的排列 12354和12345，排列12345在前，排列12354在后。按照這樣的規(guī)定，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.

首先要對給定的字符集中的字符規(guī)定了一個先后關系，在此基礎上按照順序依次產生每個排列。

[例]字符集{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;
}

總結

以上就是本文關于Java語言字典序排序算法解析及代碼示例的全部內容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！

最新評論