全排列：
從n個不同元素中任取m（m≤n）個元素，按照一定的順序排列起來，叫做從n個不同元素中取出m個元素的一個排列。當m=n時所有的排列情況叫全排列。
例如：
1 、2 、3三個元素的全排列為：
{1，2，3}，{1，3，2}，{2，1，3}，{2，3，1}，{3，1，2}，{3，2，1}。
------------------------------------------------------
解法1（遞歸）
如下圖：要對1、2、3、4進行排序，第一個位置上的元素有四種可能：1或2或3或4，假如已經確定了第一個元素為4，剩下的第二個位置上可以是1、2、3，很顯然這具有遞歸結構，如果原始要排列的數組順序為1、2、3、4，現在只要分別交換1、2，1、3，1、4然后對剩下的3個元素進行遞歸的排列。
代碼：
-----------------------------------------------
|
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
|
public void Permutation(char chs[],int start ) { if(start==chs.length-1) { Arrays.toString(chs); //如果已經到了數組的最后一個元素，前面的元素已經排好，輸出。 } for(int i=start;i<=chs.length-1;i++) { //把第一個元素分別與后面的元素進行交換，遞歸的調用其子數組進行排序 Swap(chs,i,start); Permutation(chs,start+1); Swap(chs,i,start); //子數組排序返回后要將第一個元素交換回來。 //如果不交換回來會出錯，比如說第一次1、2交換，第一個位置為2，子數組排序返回后如果不將1、2 //交換回來第二次交換的時候就會將2、3交換，因此必須將1、2交換使1還是在第一個位置 } } public void Swap(char chs[],int i,int j) { char temp; temp=chs[i]; chs[i]=chs[j]; chs[j]=temp; } |
遞歸方法會對重復元素進行交換比如使用遞歸對{1，1}進行全排序會輸出：{1，1}，{1，1}兩個重復的結果。要在排序的時候去掉重復結果，可以修改一下代碼如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public static void Permutation(char chs[],int start) { if(start==end) { list.add(new String(chs)); } for(int i=start;i<=chs.length-1;i++) { if(i==start||chs[i]!=chs[start]) { //在排列的時候進行判斷如果后面的元素與start相同時就不進行排序。 //這樣就可以避免對重復元素進行排序 Swap(chs,i,start); Permutation(chs,start+1); Swap(chs,i,start); } } } |
解法2（字典序法）
字典序法
對給定的字符集中的字符規定了一個先后關系，在此基礎上規定兩個全排列的先后是從左到右逐個比較對應的字符的先后。
列如：對a、b、c進行排序的結果是{a,b,c}、{a,c,b}、{b,a,c}、{b,c,a}、{c,a,b}、{c,b,a}
字典序法的優點是排列的結果按照順序輸出并且對于重復的元素不進行重復排序。
字典排序法的思想：
例如：對元素1，2，3，4進行排序，假設默認的數組順序為{1，2，3，4}，先輸出第一個排列：1、2、3、4。然后從右向左找到第一個非遞增的數，4，3，因為3比4小，交換3、4，并且對3后面的數進行逆序排列，第二個排列為{1，2，4，3}，再從右向左3，4，2，發現2比4小，交換從右向左第一個比2大的數，交換后{1，3，4，2}再對3后面的數進行逆序排列第三個序列為：{1，3，2，4}
依次循環直到數組成為完全遞減數組結束1、2、3、4字典排序的最大序列為{4，3，2，1}。
--------------------------------------------
代碼
-------------------------------------------
|
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
public void PermutationWithDictionary(char chs[]) { Arrays.sort(chs); //先對數組的元素進行依次排序 while(true) { System.out.println(chs); int j=chs.length-1; int index=0; for(j=chs.length-2;j>=0;j--) { if(chs[j]<chs[j+1]) { index=j; break; //從右向左找到第一個非遞增的元素 } else if(j==0){ return; } } for(j=chs.length-1;j>=0;j--) { if(chs[j]>chs[index]) break; //從右向左找到第一個比非遞增元素大的元素 } Swap(chs,index,j); //交換找到的兩個元素 Reverse(chs,index+1); //對非遞增元素位置后面的數組進行逆序排列 } } public static void Reverse(char chs[],int i) { int k=i,j=chs.length-1; while(k<j) { Swap(chs,k,j); k++; j--; } } public static void Swap(char chs[],int i,int j) { char temp; temp=chs[i]; chs[i]=chs[j]; chs[j]=temp; } |
以上這篇全排列算法-遞歸與字典序的實現方法(Java) 就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
