溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關JAVA如何用遞歸實現全排列算法，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
求一個n階行列式，一個比較簡單的方法就是使用全排列的方法，那么簡述以下全排列算法的遞歸實現。
首先舉一個簡單的例子說明算法的原理，既然是遞歸，首先說明一下出口條件。以[1, 2]為例
首先展示一下主要代碼(完整代碼在后面)，然后簡述
//對數組array從索引為start到最后的元素進行全排列 public void perm(int[]array,int start) {
if(start==array.length) { //出口條件
for(int i=0;i<array.length;i++) {
// this.result[row][i] = array[i];
System.out.print(array[i]+" ");
}
// System.out.print(++this.row+": ");
// System.out.println("逆序數是："+ this.against(array));
System.out.print('\n');
}
else {
for(int i=start;i<array.length;i++) {
swap(array,start,i); //交換數組array中索引為start與i的兩個元素
perm(array,start+1);
swap(array,start,i);
}
}
}首先數組[1, 2]分析，在else的部分
調用了swap(array, 0,0)然后調用perm(array, 1)
調用swap(array, 1, 1)然后調用perm(array, 2)，然后在if里面2 == 2成立，打印[1, 2]
調用swap(array, 1,1)把之前交換的swap(array,1,1)復原，雖然看起來沒有變化
回到上一層
調用swap(array, 0, 1) 然后調用perm(array, 1)
調用swap(array, 1, 1)然后調用perm(array, 2)，然后在if里面2 == 2成立，打印[2, 1]
調用swap(array, 1,1)把之前交換的swap(array,1,1)復原，雖然看起來沒有變化
回到上一層
跳出循環，程序結束。
這就是對[1, 2]的全排列。
那么放到一般情況，[1, 2, 3]呢？
調用了swap(array, 0,0)然后調用perm(array, 1)
然后對[2, 3]進行全排列，其中輸出[1,2,3]， [1, 3, 2]
再次調用swap(array,0,0)復原
調用了swap(array, 0,1)然后調用perm(array, 1)
然后對[1,3]進行全排列，輸出[2,1,3], [2,3,1]
再次調用swap(array,0,1)復原
調用了swap(array, 0,2)然后調用perm(array, 1)
然后對[2,1]進行全排列，輸出[3,2,1], [3,1,2]
再次調用swap(array,0,2)復原
更高階的就是同理了！
那么我們的代碼如下：
package matrix;
import java.util.Arrays;
public class Permutation {
/**
* author:ZhaoKe
* college: CUST
*/
//當前打印的第幾個排列
private int row = 0;
//存儲排列的結果
private int[][] result;
public Permutation(int[] array) {
this.row = 0;
this.result = new int[this.factor(array.length)][array.length];
}
public int[][] getResult() {
return result;
}
//求數組a的逆序數
public int against(int a[]) {
int nn = 0;
for (int i = 0; i < a.length-1; i++) {
for (int j = i+1; j<a.length; j++) {
if (a[i] > a[j]) {
nn++;
}
}
}
return nn;
}
//排列數
public int factor(int a) {
int r = 1;
for (; a>=1; a--) {
r *= a;
}
return r;
}
public void perm(int[]array,int start) {
if(start==array.length) {
System.out.print((this.row+1)+": ");
for(int i=0;i<array.length;i++) {
this.result[row][i] = array[i];
System.out.print(array[i]+" ");
}
this.row++;
System.out.println("逆序數是："+ this.against(array));
System.out.print('\n');
}
else {
for(int i=start;i<array.length;i++) {
swap(array,start,i);
perm(array,start+1);
swap(array,start,i);
}
}
}
public void swap(int[] array,int s,int i) {
int t=array[s];
array[s]=array[i];
array[i]=t;
}
public void printResult() {
for (int i = 0; i < result.length; i++) {
System.out.println(Arrays.toString(this.result[i]));
}
}
public static void main(String[] args) {
int[] a = {1, 2, 3};
Permutation p = new Permutation(a);
p.perm(a,0);
p.printResult();
}
}運行該程序結果如下：
1: 1 2 3 逆序數是：0
2: 1 3 2 逆序數是：1
3: 2 1 3 逆序數是：1
4: 2 3 1 逆序數是：2
5: 3 2 1 逆序數是：3
6: 3 1 2 逆序數是：2
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
關于JAVA如何用遞歸實現全排列算法就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
