组合

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

        // 从n个元素中取m个的各种组合形式
        f2(data, 2);
    }

    /**
     * 求全组合
     * 
     * @param data
     */
    private static void f1(int[] data) {
        fullCombination(data,new boolean[data.length],0);
        System.out.println("count_fullCombination="+count_fullCombination);
    }

    /**
     * 【用递归的思想求解全组合】
     * 数组有n个元素，那么用一个长度为n的数组记录每一位上的数取或不取的情况
     * k为当前关注的位置，本次操作处理完k位置的数后将其余的事情踢皮球给下级处理
     * 【递归解法：全组合：共有2的n次-1种】
     * @param data
     */
    private static void fullCombination(int[] data,boolean[] flag,int k) {
        if(k==data.length){
            
            boolean f=false;
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<data.length;i++){
                if(flag[i]){
                    f=true;
                    sb.append(data[i]+" ");
                }
            }
            if(f){
                count_fullCombination++;
                System.out.println(sb.toString());
            }
            return;
        }
        
        // 选取当前位置
        flag[k]=true;
        fullCombination(data, flag, k+1);
        flag[k]=false;
        // 不选
        flag[k]=false;
        fullCombination(data, flag, k+1);
        
    }

    /**
     * 从数组中取m个数出来的各种组合形式
     */
    private static void f2(int[] data, int m) {
        
//      combination1(data,m);
        combination1(data,m,0,new boolean[data.length],0);
    }

    /**
     * 用循环嵌套求解
     * 【非递归解法】
     * @param data
     * @param m
     */
    private static void combination1(int[] data, int m) {
        // 设：求从数组中取3个元素
        for(int i=0;i<data.length;i++){
            for(int j=i+1;j<data.length;j++){
                for(int k=j+1;k<data.length;k++){
                    System.out.println(String.format("%s %s %s",data[i],data[j],data[k]));
                }
            }
        }
    }
    
    /**
     * 【递归解法】
     * @param data
     * @param m:从数组中选取m个元素出来
     * @param k:当前关注的位置
     * @param a:缓存递归过程中的选择
     * @param cur_count:选取的元素个数
     */
    private static void combination1(int[] data,int m,int k,boolean[] flag,int cur_count){
        if(k==data.length){
            if(cur_count==m){
                boolean f=false;
                StringBuilder sb=new StringBuilder();
                for(int i=0;i<data.length;i++){
                    if(flag[i]){
                        f=true;
                        sb.append(data[i]+" ");
                    }
                }
                if(f){
                    count_Combination++;
                    System.out.println(sb.toString());
                }
                
            }
            return;
        }
        // 选取
        flag[k]=true;
        cur_count++;
        combination1(data,m,k+1,flag,cur_count);
        flag[k]=false;
        cur_count--;
        // 不选
        flag[k]=false;
        combination1(data,m,k+1,flag,cur_count);
    }
}

上述代码中列出了

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