排列

/**
 * 
* <p>Description: 
* 1,求全排列的非递归、递归方法
* 2，从n个数中取m个数的所有排列形式
* </p>  
* @author 杨丽金  
* @date 2018-5-2  
* @version 1.0
 */
public class 排列 {
    private static int count_fullPermutation1=0;
    private static int count_fullPermutation2=0;
    private static int count_Permutation=0;
    public static void main(String[] args) {
        int[] data={1,2,3,4};
        // 输出全组合的排列形式
        f1(data);
        
        // 输出从n个元素中取m个出来的排列形式
        f2(data,2);
    }

    

    /**
     * 输出数组data中的数的全排列
     * @param data
     */
    private static void f1(int[] data) {

        System.out.println("*******全排列输出*******");
        fullPermutation(data);
        System.out.println("count_fullPermutation1="+count_fullPermutation1);
        fullPermutation2(data,0);
        System.out.println("count_fullPermutation2="+count_fullPermutation2);
    }

    
    /**
     * 1，在数组长度已知的情况下用循环嵌套方法
     * 缺点：不能动态扩展，没有普适性
     * 【非递归解法】
     * @param data
     */
    private static void fullPermutation(int[] data) {
        // 例如数组长度为4
        // 保存某位上的数字是否已被使用
        boolean[] flag=new boolean[data.length];
        // 1,
        for(int i=0;i<data.length;i++){
            flag[i]=true;
            // 2,
            for(int j=0;j<data.length;j++){
                if(flag[j]){
                    continue;
                }
                flag[j]=true;
                // 3,
                for(int k=0;k<data.length;k++){
                    if(flag[k]){
                        continue;
                    }
                    flag[k]=true;
                    // 4,
                    for(int t=0;t<data.length;t++){
                        if(flag[t]){
                            continue;
                        }
                        flag[t]=true;
                        count_fullPermutation1++;
                        System.out.println(String.format("%s %s %s %s",data[i],data[j],data[k],data[t]));
                        flag[t]=false;// 在该种选择下得到了结果后，回溯
                    }
                    flag[k]=false;// 回溯
                }
                flag[j]=false;
            }
            flag[i]=false;
        }
    }
    
    /**
     * 所以用递归的方式进行求解
     * 这样的递归是不行的，会陷入死循环
     * @param data
     */
    /*private static void fullPermutation2(int[] data){
    }*/
    
    /**
     * 递归思路是：先选定一个数，然后对其后面的数再进行全排列
     * 【非递归解法】
     * @param data
     * @param k:当前关注的位置
     */
    private static void fullPermutation2(int[] data,int k){
        if(k==data.length){
            //
            count_fullPermutation2++;
            for(int i=0;i<data.length;i++){
                System.out.print(data[i]+" ");
            }
            System.out.println();
            return;
        }
        for(int i=k;i<data.length;i++){
            swap(data,i,k);
            fullPermutation2(data,k+1);
            swap(data,i,k);
        }
    }
    
    private static void swap(int[] data, int i, int k) {
        int temp=data[i];
        data[i]=data[k];
        data[k]=temp;
    }


    /**
     * 从数组data中取m个数的各种排列形式输出
     * @param data
     * @param m
     */
    private static void f2(int[] data,int m) {
        System.out.println("*******从数组中取m个出来的各种排列形式*******");
        permutation(data,m,0);
        System.out.println("count_Permutation="+count_Permutation);
        permutation2(data);
    }
    
    /**
     * 从数组data中取m个数的各种排列形式输出
     * 【递归解法】
     * @param data
     * @param m
     * @param k:当前需要关注的位置
     */
    private static void permutation(int[] data, int m,int k){
        if(k==m){
            count_Permutation++;
            for(int i=0;i<m;i++){
                System.out.print(data[i]+" ");
            }
            System.out.println();
            return;
        }
        for(int i=k;i<data.length;i++){
            swap(data,k,i);
            permutation(data,m,k+1);
            swap(data,k,i);
        }
    }
    
    /**
     * 从数组data中取m个数的各种排列形式输出
     * 【非递归解法】
     * @param data
     * @param m
     */
    private static void permutation2(int[] data){
        for(int i=0;i<data.length;i++){
            swap(data,0,i);
            for(int j=1;j<data.length;j++){
                System.out.println(data[0]+" "+data[j]);
            }
            swap(data,0,i);
        }
    }
}

上述代码中列出了

• 全排列的非递归、递归解法
• 从n个数中取m个的各种排列形式输出