递归处理数字全排列算法

问题背景###

递归很常用，但确实不好理解，下边这段程序是用来进行数字全排列的
由于很多算法需要讲数字全排列后再来暴力求解问题，所以学会数字的全排列还是很有意义的
比如，讲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);
    }

}

运行结果###

K(EHS80Q(I5Z0`G%SY7@~@3.png

![34W$%HUHI~HXF3L3C68]TEA.png](https://img.haomeiwen.com/i3403753/0b95f6d56af6b7ed.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)