遞歸處理數字全排列算法

問題背景###

遞歸很常用，但确實不好了解，下邊這段程式是用來進行數字全排列的

由于很多算法需要講數字全排列後再來暴力求解問題，是以學會數字的全排列還是很有意義的

比如，講1、2全排列後是1 2 和2 1

直接上java代碼###

package permuta;

import java.util.Scanner;

public class Permutation {

    public static void permutation(int n,int A[],int cur){
        
        int i,j;
        //如果一旦驗證滿了n位數，就将這個數列印出來
        if(cur==n){
            for(i=0;i<n;i++)
            System.out.print(A[i]);
            System.out.println("\n");
            return ;
        }
        
        for(i=1;i<=n;i++){      
            int ok=1;
            for(j=0;j<cur;j++){
                if(A[j]==i)
                    ok=0;
            }
            //從左邊位數開始放數，如果這個位數沒有放過，這個位置就放i，放完之後的事就遞歸，交給别人去幹了，就可以考慮下一個位數了
            if(ok==1){
                A[cur]=i;
                permutation(n, A, cur+1);//遞歸
            }
        }
        
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int n,cur=0;
        int A[]={1,2,3,4,5,6,7,8,9};
        System.out.println("請輸入你要全排列的個數");
        Scanner scanner=new Scanner(System.in);
        n=scanner.nextInt();
        permutation(n, A, cur);
    }

}           

複制

運作結果###

(http://upload-images.jianshu.io/upload_images/3403753-0b95f6d56af6b7ed.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)