递归(2)

递归实现全排列

【算法讲解】

设R={r1,r2,…,rn}是要进行排列的n个元素，Ri=R-{ri}。
集合X中元素的全排列记为perm(X)。
(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。
R的全排列可归纳定义如下：
当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；
当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。
实现思想：将整组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。

【示例】

当n=3，并且E={a，b，c}，则：
perm(E)=a.perm({b,c}) + b.perm({a,c}) + c.perm({a,b})
perm({b,c})=b.perm(c) + c.perm(b)
a.perm({b,c})=ab.perm(c) + ac.perm(b)
=ab.c + ac.b=(abc, acb)

/**
 * 全排列的递归
 * @author lenovo
 *
 */
public class Main {
    public static void main(String[] args) {
        int arr[]={1,2,3};
        perm(arr,0,2);
    }
    public static void perm(int [] arr,int k,int m){
        if(k==m){
            for(int i=0;i<=m;i++){
                System.out.print(arr[i]);
            }
            System.out.println();
        }else{
            for(int i=k;i<=m;i++){
                Swap(arr,k,i);
                perm(arr,k+1,m);
                Swap(arr,k,i);
            }
        }    
    }
    public static void Swap(int []arr,int m ,int n){
        int t;
        t = arr[m];
        arr[m] = arr[n];
        arr[n] = t;
    }
}