減治法在生成組合對象問題中的應用

在深入淺出講算法思想--蠻力法思想分析及應用這篇文章的最優解問題中中已經初步講解了這類應用，下面我們將使用減治法再次思考這類問題。

1、全排列問題，在數學中求解一個n個數組合的全排列問題會產生n！個組合的情況。暴力枚舉的確是個方法，但是除非n非常的小，不然這個時間復雜度是非常龐大的，但是如果運用減治思想就可以解決這種問題，我們便可以將我們可以將生成n！個排雷的問題變為求解(n-1)！個全排列的問題，之后再將n插入n-1個元素每種排列中n可能的位置中去。因為n*(n-1)!=n!，所以這就是該算法的可行性分析。

1）簡單回溯實現：

public class Main {static int[] a = new int[4];static int[] visit = new int[4];public static void main(String[] args) {int n = 3;f(0, n);}private static void f(int cur, int n) {if (cur == n) {for (int i = 0; i < n; i++) {if ((i+1) % 3 == 0) {System.out.print(a[i] + " ");System.out.println();} else {System.out.print(a[i] + " ");}}}for (int i = 1; i <= n; i++) {if (visit[i] == 0) {visit[i] = 1;a[cur] = i;f(cur+1, n);visit[i] = 0;}}} } 2）Johnson-Trotter算法實現：參考 johnson_trotter(生成排列算法)

3）字典序實現：第二種算法實現的結果輸出是從最后一個開始的，不過，按照習慣上的寫法，我們總是希望結果是按照升序排列的，而字典序可以實現這種即高效又是升序的效果。

public class Main {public static void main(String[] args) {int arr[] = new int[]{1,2,3};sort(arr);for (int i = 0; i < arr.length; i++) {System.out.print(arr[i]);}System.out.println();while(nextPermutation(arr)){for(int value : arr)System.out.print(value);System.out.println();}}public static boolean nextPermutation(int[] arr){int pos1 = 0;int pos2 = 0;/*** 找到使得a[i] < a[i+1]的最大的i，賦給pos1* 用于將123變為132這樣的情況* */int flag = 0;for(int i = arr.length - 2;i >= 0;i--) {if(arr[i] < arr[i + 1]) {pos1 = i;flag = 1;break;}}if(flag == 0) {return false;}/*** 找到使得a[i]<a[j]的最大的j，賦給pos2* 用于362541變為364125這樣的情況* */for(int j = pos1 + 1;j < arr.length;j++) {if(arr[j] > arr[pos1]) {pos2 = j;}}/*** 交換a[pos1]與a[pos2]* */int temp = arr[pos1];arr[pos1] = arr[pos2];arr[pos2] = temp;/*** 對a[i+1]到a[n]逆序* */for (int i = pos1+1; i < arr.length; i++) {for (int j = arr.length-1; j > i ; j--) {temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}return true;}/*** 冒泡* */public static void sort(int[] arr) {for(int i = 0;i < arr.length - 2;i++) {for(int j = 0;j < arr.length - i - 1;j++) {if(arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}} }

總結

以上是生活随笔為你收集整理的减治法在生成全排列中的应用（JAVA）--回溯、Johnson-Trotter算法、自字典序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。