字典序法就是按照字典排序的思想逐一產(chǎn)生所有排列。
在數(shù)學(xué)中，字典或詞典順序（也稱為詞匯順序，字典順序，字母順序或詞典順序）是基于字母順序排列的單詞按字母順序排列的方法。 這種泛化主要在于定義有序完全有序集合（通常稱為字母表）的元素的序列（通常稱為計算機(jī)科學(xué)中的單詞）的總順序。
對于數(shù)字1、2、3......n的排列，不同排列的先后關(guān)系是從左到右逐個比較對應(yīng)的數(shù)字的先后來決定的。例如對于5個數(shù)字的排列 12354和12345，排列12345在前，排列12354在后。按照這樣的規(guī)定，5個數(shù)字的所有的排列中最前面的是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ī)定了一個先后關(guān)系，在此基礎(chǔ)上按照順序依次產(chǎn)生每個排列。
[例]字符集{1,2,3},較小的數(shù)字較先,這樣按字典序生成的全排列是:123,132,213,231,312,321。
生成給定全排列的下一個排列，所謂一個的下一個就是這一個與下一個之間沒有字典順序中相鄰的字符串。這就要求這一個與下一個有盡可能長的共同前綴，也即變化限制在盡可能短的后綴上。
后一個排列與前一個排列之間存在一定的關(guān)系，后一個排列的求解過程如下：
設(shè)有排列(p)=2763541，按照字典式排序，它的下一個排列是什么？
2763541 （找最后一個正序35）
2763541 （找3后面比3大的最后一個數(shù)4）
2764531（交換3,4的位置）
2764135 （把4后面的5,3,1反轉(zhuǎn)）
下面給出求 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]
反轉(zhuǎn) p[j] 后面的數(shù)得到 p[1] …p[i-2] p[j] p[n] … p[j+1] p[i-1] p[j-1] … p[i]
代碼實現(xiàn)如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
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; } } //已經(jīng)到最后一個排列了 全部是逆序 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;} |
總結(jié)
以上就是本文關(guān)于Java語言字典序排序算法解析及代碼示例的全部內(nèi)容，希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對本站的支持！
原文鏈接：http://blog.csdn.net/zhhtao89/article/details/50394347
