全排列的兩種實現方式(java)-poj2718
- 2019 年 10 月 6 日
- 筆記
以前遇到的全排列，清一色的dfs回溯，自己知道時間複雜度挺高的，最近遇到poj2718認真總結了下全排列。
全排列：給定幾個數，要求找出所有的排列方式。
法一：dfs回溯法：
- 思路：回溯法的核心思路就是模擬過程，其實它相對簡單因為你往往不需要考慮它的下一步是什麼，你只需關注如果操作這些數。你往往可能不在意數的規則規律但是也能搞出來。
- 舉個例子。有1，2，3，4，5五個數需要全排列。我用回溯法的話我可以用附加的數組，或者list，boolean數組等添加和刪除模擬的數據。
- 比如第一次你可以循環將第一個賦值（1-5）,在賦值每個數的時候標記那些用過，那些還能用的數據，執行dfs一直到底層。然後dfs執行完要將數據復原。比如標記的數據進行取消標記等等。
詳細程式碼為
import java.util.Scanner; public class quanpailie1 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String s[]=sc.nextLine().split(" "); int a[]=new int[s.length]; for(int i=0;i<s.length;i++) { a[i]=Integer.parseInt(s[i]); } int b[]=new int[a.length]; boolean b1[]=new boolean[a.length];//判斷是否被用 long startTime = System.currentTimeMillis(); dfs(b1,a,b,0); long endTime = System.currentTimeMillis(); System.out.println("運行時間:" + (endTime - startTime) + "ms"); } private static void dfs(boolean[] b1, int[] a, int b[], int index) { // TODO Auto-generated method stub int len=a.length; if(index==a.length)//停止 { if(b[0]==0) {} else { for(int j:b) { System.out.print(j+" "); } System.out.println(); } } else for(int i=0;i<len;i++) { if(!b1[i]) { b[index]=a[i]; b1[i]=true;//下層不能在用 dfs(b1, a, b,index+1); b1[i]=false;//還原 } } } }
輸出列印結果為：
輸入： 1 2 3 4 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 運行時間:2ms
法二：遞歸法
上述方法雖然能夠實現全排列，但是方法的複雜度還是很高。指數級別增長。因為要遍歷很多沒用的情況。所以當數據較大並不能高速處理。所以換一種思路處理。 設[a,b,c,d]為abcd的全排列 那麼，該全排列就是 [1,2,3,4]（四個數的全排列）=
- 1 [2,3,4]（1開頭[2,3,4]的全排列）=
- 1 4 3 [2]=1 4 3 2
- 1 4 2 [3]=1 4 2 3
- 1 3 2 [4]=1 3 2 4
- 1 3 4 [2]=1 3 4 2
- 1 2 3 [4] =1 2 3 4(1 2 3 開頭的[4]全排列)
- 1 2 4 [3]=1 2 3 4
- 1 2 [3,4] (1,2開頭的[3,4]全排列)
- 1 3 [2,4]
- 1 4 [3,2]
- 2 [1,3,4]=
- 2 4 3 [1]=2 4 3 1
- 2 4 1 [3]=2 4 1 3
- 2 3 1 [4]=2 3 1 4
- 2 3 4 [1]=2 3 4 1
- 2 1 3 [4]=2 1 3 4
- 2 1 4 [3]=2 1 4 3
- 2 1 [3,4]
- 2 3 [1,4]
- 2 4 [3,1]
- 3 [2,1,4]=(略)
- 3 2 [1,4]
- 3 1 [2,4]
- 3 4 [3,2]
- 4 [2,3,1]=(略)
- 4 2 [3,1]
- 4 3 [2,1]
- 4 1 [3,2]
對於全排列遞歸的模式為：（和dfs很像）
- isstop?: 判斷遞歸終止
- before recursive()
- recursive()
- after recursive()
- stop
- do not stop:
根據上面的數據找點規律吧：
- 上面是遞歸沒毛病。整個全排列就是子排列遞歸到最後遍歷的所有情況
- 千萬別被用回溯的獲得全排列的數據影響。部落客之前卡了很久一直想著從回溯到得到的數據中找到遞歸的關係，結果寫著寫著就寫崩了。
- 遞歸的數據有規律。它只關注位置而不關注數據的大小排列。意思是說你不需要糾結每一種排列的初始態是啥。你只要關注他有那些數就行，舉個例子，出台為1 [2,3,4]和1 [4,3,2]的效果一樣，你需要關注的是1這個部分。1這個部分處理好遞歸自然會處理好子節點的關係。
- 對於同一層級 比如1[],2[],3[],4[],例如1，2，3，4而言，每一層如下的步驟，可以保證同層數據可靠，並且底層按照如下思路也是正確的。
- 1,2,3,4—>swap(0,0)—>1 [2 3 4] (子遞歸不用管)—>swap(0,0)—>1,2,3,4
- 1,2,3,4—>swap(0,1)—>2 [1 3 4] (子遞歸不用管)—>swap(0,1)—>1,2,3,4
- 1,2,3,4—>swap(0,2)—>3 [2 1 4] (子遞歸不用管)—>swap(0,1)—>1,2,3,4
- 1,2,3,4—>swap(0,3)—>4 [2 3 1] (子遞歸不用管)—>swap(0,1)—>1,2,3,4
- 所以整個全排列函數大致為：
- swap(start,i)//i是從該層後面所有可能的全部要選一次排列到該層
- recursive(start+1)//該層確定，進入下一層子遞歸
- swap(start,i)//因為不能影響同層之間數據，要保證數據都是初始話 具體程式碼為：
- 停止
- 不停止: -for(i from start to end)
import java.util.Scanner; public class quanpailie2 { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); String s[] = sc.nextLine().split(" "); int a[] = new int[s.length]; for (int i = 0; i < s.length; i++) { a[i] = Integer.parseInt(s[i]); } long startTime = System.currentTimeMillis(); arrange(a, 0, a.length - 1); long endTime = System.currentTimeMillis(); System.out.println("運行時間:" + (endTime - startTime) + "ms"); } static void arrange(int a[], int start, int end) { if (start == end) { for (int i : a) { System.out.print(i); } System.out.println(); return; } for (int i = start; i <= end; i++) { swap(a, i, start); arrange(a, start + 1, end); swap(a, i, start); } } static void swap(int arr[], int i, int j) { int te = arr[i]; arr[i] = arr[j]; arr[j] = te; } }
輸入輸出結果為：
1 2 3 4 1234 1243 1324 1342 1432 1423 2134 2143 2314 2341 2431 2413 3214 3241 3124 3142 3412 3421 4231 4213 4321 4312 4132 4123 運行時間:1ms
你可以發現兩者採用的規則不同，輸出的數據到後面是不一樣的。但是你可能還沒體驗到大數據對程式運行的影響。我把輸出的結果注釋掉。用0 1 2 3 4 5 6 7 8 9進行全排序：
對於全排列，建議能採用遞歸還是遞歸。因為遞歸沒有額外數組開銷。並且計算的每一次都有用。而回溯會有很多無用計算。數只越大越明顯。
poj2718
題意就是給幾個不重複的數字，讓你找出其中所有排列方式中組成的兩個數的差值最小。除了大小為0否則0不做開頭。
思路：全排列所有情況。最小的一定是該全排列從中間分成2半的數組差。要注意的就是0的處理，不日3個長度的0開頭/其他長度的0開頭等等。還有的人採用貪心剪枝。個人感覺數據並沒有那麼有規律貪心不一定好處理，但是你可以適當剪枝減少時間也是可以的。比如根據兩個數據的首位 相應剪枝。但這題全排列就可以過。
還有一點就是：數據加減乘除轉換，能用int就別用String，string轉起來很慢會超時。
附上ac程式碼，程式碼可能並不漂亮，前面的介紹也可能有疏漏，還請大佬指出！
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; public class poj2718 { static int min = Integer.MAX_VALUE; static int mid = 0; public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); int t = Integer.parseInt(in.readLine()); for (int q = 0; q < t; q++) { String s[] = in.readLine().split(" "); int a[] = new int[s.length]; for (int i = 0; i < s.length; i++) { a[i] = Integer.parseInt(s[i]); } min = Integer.MAX_VALUE; mid = (a.length) / 2; arrange(a, 0, a.length - 1); out.println(min); out.flush(); } } static void arrange(int a[], int start, int end) { if (start == end) { // for(int i:a) // { // System.out.print(i); // } // System.out.println(); if ((a[0] == 0 && mid == 1) || (a[mid] == 0 && a.length - mid == 0) || (a[0] != 0 && a[mid] != 0)) { int va1 = 0; int va2 = 0; for (int i = 0; i < mid; i++) { va1 = va1 * 10 + a[i]; } for (int i = mid; i < a.length; i++) { va2 = va2 * 10 + a[i]; } min = min < Math.abs(va1 - va2) ? min : Math.abs(va1 - va2); } return; } for (int i = start; i <= end; i++) { swap(a, start, i); arrange(a, start + 1, end); swap(a, start, i); } } static void swap(int arr[], int i, int j) { int te = arr[i]; arr[i] = arr[j]; arr[j] = te; } }
dfs回溯法github鏈接https://github.com/javasmall/oj-problem-java/blob/master/%E6%A8%A1%E6%9D%BF/src/%E5%85%A8%E6%8E%92%E5%88%97/quanpailie1.java
遞歸法全排列github鏈接 https://github.com/javasmall/oj-problem-java/blob/master/%E6%A8%A1%E6%9D%BF/src/%E5%85%A8%E6%8E%92%E5%88%97/quanpailie2.java
poj2718程式碼github鏈接 https://github.com/javasmall/oj-problem-java/blob/master/poj/src/%E6%90%9C%E7%B4%A2/poj2718.java
如有錯誤還請大佬指正。
