目錄

一、陣列元素的組合

二、陣列元素的全排列

三、陣列元素的排列組合

Hello，你好呀，我是灰小猿！一個超會寫bug的程式猿！

最近在做藍橋杯相關的試題的時候發現對陣列元素進行排列組合的使用十分的廣泛，而常見的排列組合型別的題目也是資料結構和演算法的典型例題，所以今天在這里和大家分享一下我們在平常的開發程序中，常會用到的幾種排列組合的型別和解法：

一、陣列元素的組合

對于從n個元素的陣列arr中取出m個數（不考慮順序且不重復）放到新陣列newarr中的情況，常見的思路是使用遞回的思想：

1. 從陣列arr中取出n個數，那么我們可以先取出arr的第一個數作為newarr的第一個元素
2. 取出arr的第一個元素之后，從后面的n-1個元素中取出m-1個元素，（這是第一步的子問題）采用遞回實作，
3. 當需要取出0個元素時，一個組合的任務完成
4. 回到第一步，利用for回圈接著取出第二個元素（開始下一個組合），一共回圈n-m次即可

具體的實作可以查看下面的函式，可直接呼叫使用：

    /**
	 * 在陣列中選取n個數進行組合（不考慮順序且資料不重復）
	 * @param 待處理的陣列
	 * @param newarr 組合后得到的陣列
	 * @param k  從哪一個下標的元素開始取
	 * @param n 需要取出元素的個數
	 * */
	private static void combination(int[] arr,int[] newarr, int k,int n) {
		//當需要取出的元素個數是0時，說明組合完成
		if (n==0) {
			for (int i = 0; i < newarr.length; i++) {
				System.out.print(newarr[i]);
			}
			System.out.println();
			return;
		}
		for (int i = k; i <= arr.length-n; i++) {		
			newarr[newarr.length-n] = arr[i];	//將提取出來的數依次放到新陣列中
			combination(arr, newarr,i+1, n-1);	//按照同樣的方法從剩下的元素中選出n-1個元素
		}
	}

測驗用例：

public static void main(String[] args) {
		int[] arr = {1,2,3,4};		//待處理的陣列
		int n = 3;	//取出元素的個數
		int[] newarr = new int[n];		//存放結果的陣列
		combination(arr, newarr, 0, n);
	}

二、陣列元素的全排列

對于將有n個數的陣列arr進行全排列，所采用的思想是遞回加回溯，

1. 對n個元素進行全排列，將第一個元素依次和之后的元素互換，將第一個元素確定下來
2. 對之后的n-1個元素進行全排列，（可以看做是第一步的子問題）采用遞回實作
3. 將互換后的元素重新換回來，以防止陣列元素的順序被打亂（回溯思想）

具體的實作可以看下面的函式，（可以直接使用）

    /**
	 * 對陣列中所有的元素進行全排列
	 * @param arr 待排列的陣列
	 * @param k 確定第幾個元素，是下標，從0開始
	 * */
	private static void f(int[] arr, int k) {
		//當k等于陣列的長度時，說明排列完成
		if (k == arr.length) {
			//將排列好的陣列輸出
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i]);
			}
			System.out.println();
		}
		
		for (int i = k; i < arr.length; i++) {
			//將待確定的元素位置和后面的元素互換
			int t = arr[k];
			arr[k] = arr[i];
			arr[i] = t;
			
			//遞回（確定第k+1個元素）
			f(arr, k+1);
			
			//回溯，將調換后的元素重新調換回來
			t = arr[k];
			arr[k] = arr[i];
			arr[i] = t;
		}	
	}

測驗用例：

public static void main(String[] args) {
		int[] arr = {1,2,3,4};		//待處理的陣列
		int n = 3;	//取出元素的個數
		int[] newarr = new int[n];		//存放結果的陣列
		f(arr, 0);
	}

三、陣列元素的排列組合

有了上面對從n個元素的陣列arr中取出m個數（不考慮順序且不重復）和對n個數進行全排列的理解，那么對于從n個數中取出m個數實作排列的問題，可以看成是上面兩個問題的結合體，

按照數學中的思路，我們可以先從n個元素的陣列中選取出m個元素，之后對這m個元素進行全排列即可，

實作的方法如下：

    /**
	 * 陣列中對n個數進行全排列
	 * @param 待處理的陣列
	 * @param newarr 排列后得到的陣列
	 * @param k  從哪一個下標的元素開始處理
	 * @param n 處理元素的個數
	 * */
	private static void pac(int[] arr,int[] newarr, int k,int n) {
		//當n=0時，說明選取的數的個數為0，也就是組合完成
		if (n==0) {
			f(newarr, 0);	//對組合到的新陣列進行全排列
			return;
		}
		for (int i = k; i <= arr.length-n; i++) {		
			newarr[newarr.length-n] = arr[i];
			pac(arr, newarr,i+1, n-1);
		}
	}
	
	/**
	 * 對陣列中所有的元素進行全排列
	 * @param arr 待排列的陣列
	 * @param k 確定第幾個元素，是下標，從0開始
	 * */
	private static void f(int[] arr, int k) {
		//當k等于陣列的長度時，說明排列完成
		if (k == arr.length) {
			//將排列好的陣列輸出
			for (int i = 0; i < arr.length; i++) {
				System.out.print(arr[i]);
			}
			System.out.println();
		}
		
		for (int i = k; i < arr.length; i++) {
			//將待確定的元素位置和后面的元素互換
			int t = arr[k];
			arr[k] = arr[i];
			arr[i] = t;
			
			//遞回（確定第k+1個元素）
			f(arr, k+1);
			
			//回溯，將調換后的元素重新調換回來
			t = arr[k];
			arr[k] = arr[i];
			arr[i] = t;
		}	
	}

測驗用例：

public static void main(String[] args) {
		int[] arr = {1,2,3,4};		//待處理的陣列
		int n = 3;	//取出元素的個數
		int[] newarr = new int[n];		//存放結果的陣列
		pac(arr,newarr,0, n);
	}

以上就是我們常見的三種排列組合型別及其解決方法，主要就是采用了遞回和回溯的思想，其中有優化或不足的地方還希望各位提出更正，

覺得不錯記得點贊關注喲！

灰小猿陪你一起進步！