全排列演算法--遞回實作(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]

標籤：其他

上一篇：基于均值坐標(Mean-Value Coordinates)的影像融合演算法的優化實作

下一篇：對稱的二叉樹