• 计算一维组合数的java实现


    背景很简单,就是从给定的m个不同的元素中选出n个,输出所有的组合情况!

    例如:从1到m的自然数中,选择n(n<=m)个数,有多少种选择的组合,将其输出!

    本方案的代码实现逻辑是比较成熟的方案:

    * 一个bit位(boolean)一维数组中,初始化全为0(false), 然后给左边的n个位初始化为1(true)。
    * <1> 从左向右找第一个10的位置,将10换位程01,然后将这个01左边的所有的1全都移位到数组的最左边,此时得到的1所在位置下标对应序列即为一个组合数。 
    * <2> 循环重复上面的<1>步骤的操作,直到所有的1都移动到最右边为止。

    先不多说其他的,直接将代码贴在这里,以供有需要的伙伴借鉴:

      1 /**
      2  * @author "shihuc"
      3  * @date   2016年12月1日
      4  */
      5   6 
      7 import java.util.ArrayList;
      8 import java.util.Arrays;
      9 
     10 /**
     11  * @author chengsh05
     12  * 
     13  * 组合算法实现,支持产品列表页的筛选模块实现全静态化。
     14  * 
     15  * 给定m个不同的数,从中选择出n个数的不同选择方法有多少种?
     16  * 答案:一共有 n!/(n-m)!*m!
     17  * 
     18  * 存储计算出来的组合结构,组合元素之间用逗号分隔
     19  *         例如1,2,3的全组合:
     20  *         "1,", "2,", "3,","1,2,", "1,3,", "2,3,", "1,2,3,"
     21  */
     22 public class Combination {
     23     
     24     /**
     25      * 从m个元素中取出n个元素,获取排序好了的组合数列表,同一个组合中的元素按从小到大排序。
     26      * 
     27      * @param m 组合的元素基数
     28      * @param n 组合的被选元素个数
     29      * @return 排序好后的组合列表
     30      * @throws Exception 
     31      */
     32     public ArrayList<String> getCombinations(int m, int n) throws Exception{
     33         
     34         if(m < n){
     35             throw new IllegalCombinationInputException();
     36         }
     37         
     38         ArrayList<String> resCom = calcCombination(m, n);
     39         
     40         return resCom;
     41     }
     42     
     43     /**
     44      * 通过移位方式,计算给定m个数中取出n个数的组合列表。
     45      * 
     46      * 具体思路:
     47      * 一个bit位(boolean)数组中,初始化全为0(false), 然后给左边的n个位初始化为1(true)。
     48      * <1> 从左向右找第一个10的位置,将10换位程01,然后将这个01左边的所有的1全都 移位到数组的最左边,此时得到的1所在位置下标对应的序列即为一个组合数。 
     49      * <2> 循环重复上面的<1>步骤的操作,直到所有的1都移动到最右边为止。
     50      * 
     51      * @param m 输入的基数个数
     52      * @param n 组合被选元素格式
     53      * @return 原始组合数列表,即没有排序的组合
     54      */
     55     private ArrayList<String> calcCombination(int m, int n){
     56         boolean base[] = new boolean[m];
     57         Arrays.fill(base, false);
     58         for(int i=0; i<n; i++){
     59             base[i] = true;
     60         }
     61         return combination(base,m,n);
     62     }
     63     
     64     private ArrayList<String> combination(boolean a[], int m, int n){
     65         ArrayList<String> combination = new ArrayList<String>();        
     66         while(!isAllZeroLeft(a, m, n)){
     67             for(int i=0; i<m-1; i++){
     68                 if(a[i] == true && a[i+1] == false){
     69                     String elem = calcElement(a);    //计算出一个组合元素
     70                     //System.out.println(elem);
     71                     combination.add(elem);
     72                     oneZeroSwap(a, i, i+1);          //完成10/01换位                    
     73                     moveFrontOneToLeft(a, i);        //完成剩余左边的1全向最左边搬移操作                    
     74                     break;
     75                 }
     76             }
     77         }
     78         
     79         //最后一个元素也是组合的一个,即所有的1(true)都到了数组的最右边
     80         combination.add(calcElement(a));
     81         return combination;
     82     }
     83     
     84     /**
     85      * 异或操作实现不开辟新的存储空间完成两个数的位置交换。
     86      * 
     87      * @param a 待操作数所在的数组
     88      * @param x 待交换位置的第一个数在数组中的下标
     89      * @param y 待交换位置的第二个数在数组中的下标
     90      */
     91     private void oneZeroSwap(boolean a[], int x, int y){
     92         a[x] = a[x] ^ a[y];
     93         a[y] = a[y] ^ a[x];
     94         a[x] = a[x] ^ a[y];
     95     }
     96     
     97     /**
     98      * 判断10作01交换位置后,是否实现了数组a中右端的n个元素全为1(true),这个结果作为10/01换位结束标识
     99      * 
    100      * @param a 10/01换位的输入数组
    101      * @param m 计算组合的元数据个数
    102      * @param n 计算组合的被选取元素个数
    103      * @return true表示10/01换位结束,false表示还可以继续
    104      */
    105     private boolean isAllZeroLeft(boolean a[], int m, int n){
    106         int gap = m - n;
    107         for(int i=0; i<gap; i++){
    108             if(a[i]){
    109                 return false;
    110             }
    111         }
    112         return true;
    113     }
    114     
    115     /**
    116      * 将10/01换位之后数组左边的全部1都搬移到数组的最左边。
    117      * 
    118      * @param a 待操作的组合数组
    119      * @param end 指明搬移操作的范围,在end数组下标左边的进行搬移, 这个end的值小于数组的长度
    120      */
    121     private void moveFrontOneToLeft(boolean a[], int end){
    122         int oneCnt = 0;
    123         for(int i=0; i<end; i++){
    124             if(a[i]){
    125                 oneCnt++;
    126                 a[i] = false;
    127             }
    128         }
    129         for(int i=0; i<oneCnt; i++){
    130             a[i] = true;
    131         }
    132     }
    133     
    134     /**
    135      * 计算当前数组中的组合元素的值,数组元素为1(true)的对应的下标的全集,即为所需的一个组合元素值
    136      * 
    137      * @param a 待操作的组合数组
    138      * @return 一个组合的值, 去掉了最后的一个逗号分隔符
    139      */
    140     private String calcElement(boolean a[]){        
    141         String elem = "";
    142         for(int i=0; i<a.length; i++){
    143             if(a[i]){
    144                 elem += (i+1) + ",";
    145             }
    146         }
    147         return elem.substring(0, elem.length() - 1);
    148     }
    149         
    150     
    151     /**
    152      * @param args
    153      * @throws Exception 
    154      */
    155     public static void main(String[] args) throws Exception {
    156         int m = 5, n = 2;
    157         Combination combination = new Combination();
    158         ArrayList<String> coms = combination.getCombinations(m, n);
    159         for(int i = 0; i<coms.size(); i++){
    160             System.out.println(coms.get(i));
    161         }
    162     }
    163 }

     代码中定义的Exception的类:

     1 /**
     2  * @author "shihuc"
     3  * @date   2016年12月1日
     4  */
     5 
     6 /**
     7  * @author chengsh05
     8  *
     9  */
    10 public class IllegalCombinationInputException extends Exception{
    11 
    12     private static final long serialVersionUID = 678024281707796100L;
    13     
    14     public IllegalCombinationInputException(){
    15         super("The combination base number should be not less than the selection number.");  
    16     }
    17 
    18 }

    此算法思路,在很多场景下还是值得借鉴的!

    算法是计算机科学的灵魂,坚持算法学习和应用......

  • 相关阅读:
    团队冲刺2---个人工作总结一(5.25)
    第十二周学习进度
    课堂作业——找水王
    个人冲刺07
    第十五周学习进度情况
    构建之法阅读笔记06
    构建之法阅读笔记05
    第十四周学习进度情况
    个人冲刺06
    个人冲刺05
  • 原文地址:https://www.cnblogs.com/shihuc/p/6141104.html
一二三 - 开发者的网上家园