字典序法就是按照字典排序的思想逐一產生所有排列。
在數學中,字典或詞典順序(也稱為詞彙順序,字典順序,字母順序或詞典順序)是基於字母順序排列的單詞按字母順序排列的方法。 這種泛化主要在於定義有序完全有序集合(通常稱為字母表)的元素的序列(通常稱為計算機科學中的單詞)的總順序。
對於數字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;}總結
以上就是本文關於Java語言字典序排序算法解析及代碼示例的全部內容,希望對大家有所幫助。感興趣的朋友可以繼續參閱本站其他相關專題,如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!