问题描述：计算一组数据的组合数并输出

Html代码  收藏代码
  1. 例如：输入1,2,3,4,5时，大小取3，共有C(5,3)=10个组合数，  
  2. 将其从小到大依次排序可分组如下：  
  3. —-  
  4. 123   
  5. 124  
  6. 125  
  7. 134  
  8. 135  
  9. 145  
  10. —-  
  11. 234  
  12. 235  
  13. 245  
  14. —-  
  15. 345  
  16. 解题思路：求长度为 n 的source[]数组，且大小为 m 的第 x 个组合数  
  17. 1)获取组合数的第一个字符  
  18.   因为 C(n,m) = C(n-1,m-1) + C(n-2,m-1) + .. + C(m-1,m-1)  
  19.   所以可依次计算 C(n-k,m-1) [1 <= k <= n-m+1]的值，直到  
  20.   x < C(n-1,m-1) + C(n-2,m-1) + .. + C(n-k,m-1)  
  21.   这时 source[k-1] 就是组合数的第一个字符  
  22. 2)获取下一个字符  
  23.   在获取了第一个字符之后，记   
  24.   y = x – (C(n-1,m-1) + C(n-2,m-1) + .. + C(n-k+1,m-1))  
  25.   问题降级为在起始下标为 k,长度为 n-k 的source[]数组中,  
  26.   选择大小为 –m 的第 y 个组合数，因此可重复1)的过程  
  27. 3)当 m == 1时，选取组合数的最后一个字符，完成运算  
  28.     

 

Java代码  收藏代码
  1. package org.demo.algorithm;  
  2. /** 
  3.  * 计算并输出组合数 
  4.  * @author   
  5.  * @date    2010-9-13 
  6.  * @file    org.demo.algorithm.Combination.java 
  7.  */  
  8. public class Combination {  
  9.     /** 
  10.      * 测试 
  11.      * @param args 
  12.      */  
  13.     public static void main(String[] args) {  
  14.         String[] source = {“1”,“2”,“3”,“4”,“5”,“6”};  
  15.         int m = 3;  
  16.         int size = (int)getCnm(source.length,m);  
  17.         for (int i=0; i<size; i++){  
  18.             String data = getValue(source,m,i);  
  19.             System.out.println(“[” + i + “] ” + data);  
  20.         }  
  21.     }  
  22.     /** 
  23.      * 计算数组 source[] 中大小为 m 的第 x 个组合数 
  24.      * 按下述原理分组 
  25.      * C(n,m) = C(n-1,m-1) + C(n-1,m) 
  26.      * C(n,m) = C(n-1,m-1) + C(n-2,m-1) + C(n-2,m) 
  27.      * … 
  28.      * C(n,m) = C(n-1,m-1) + C(n-2,m-1) + .. + C(m,m-1) + C(m,m) 
  29.      * C(n,m) = C(n-1,m-1) + C(n-2,m-1) + .. + C(m,m-1) + C(m-1,m-1) 
  30.      * 最后一步转换是因为 C(m,m) == C(m-1,m-1) 
  31.      * @param source 
  32.      * @param m 组合数的大小，且 1 <= m <= source.length 
  33.      * @param x [0,C(n,m)) 
  34.      * @return 
  35.      */  
  36.     public static String getValue(String[] source,int m,int x){  
  37.         // 数组大小  
  38.         int n = source.length;  
  39.         // 存储组合数  
  40.         StringBuilder sb = new StringBuilder();  
  41.         int start = 0;  
  42.         while(m > 0){  
  43.             if (m == 1){  
  44.                 // m == 1 时为组合数的最后一个字符  
  45.                 sb.append(source[start + x]);  
  46.                 break;  
  47.             }  
  48.             for (int i=0; i<=n-m; i++){                        
  49.                 int cnm =  (int)getCnm(n-1-i,m-1);  
  50.                 if(x <= cnm-1){  
  51.                     sb.append(source[start + i]);  
  52.                     // 启始下标前移  
  53.                     start = start + (i + 1);  
  54.                     // 搜索区域减小  
  55.                     n = n – (i+1);  
  56.                     // 组合数的剩余字符个数减少  
  57.                     m–;  
  58.                     break;  
  59.                 } else {  
  60.                     x = x – cnm;                      
  61.                 }         
  62.             }  
  63.         }  
  64.         return sb.toString();  
  65.     }  
  66.     /** 
  67.      * 计算组合数 
  68.      * 计算组合数的推导过程如下， 
  69.      * 因为直接计算 n! 容易发生数据溢出，故可改为计算 ln(n) 
  70.      * C(n,m) = n!/(m!(n-m)!)  
  71.      * C(n,m) = n(n-1)..(n-m+1)/m! 
  72.      * ln(C(n,m)) = ln(n(n-1)..(n-m+1)/m!) 
  73.      * ln(C(n,m)) = ln(n(n-1)..(n-m+1)) – ln(m!) 
  74.      * ln(C(n,m)) = (ln(n) + ln(n-1) + .. + ln(n-m+1)) 
  75.      *             -(ln(m) + ln(m-1) + .. + ln(1)) 
  76.      * 由上可知 C(n,m) = e^ln(C(n,m)), 
  77.      * 并且由公式右侧可知，m 越小计算量越小 
  78.      * ∵ C(n,m) = C(n,n-m) 
  79.      * ∴ 当 m>n/2.0时,可改为计算 C(n,n-m) 
  80.      * @param n 
  81.      * @param m 
  82.      * @return 
  83.      */  
  84.     public static long getCnm(int n,int m){  
  85.         if (n < 0 || m < 0){  
  86.             throw new IllegalArgumentException(“n,m must be > 0”);  
  87.         }  
  88.         if (n == 0 || m == 0){  
  89.             return 1;  
  90.         }  
  91.         if (m > n){  
  92.             return 0;  
  93.         }  
  94.         if (m > n/2.0){  
  95.             m = n-m;  
  96.         }  
  97.         double result = 0.0;  
  98.         for (int i=n; i>=(n-m+1); i–){  
  99.             result += Math.log(i);  
  100.         }  
  101.         for (int i=m; i>=1; i–){  
  102.             result -= Math.log(i);  
  103.         }  
  104.         result = Math.exp(result);  
  105.         return Math.round(result);  
  106.     }  
  107. }  

 

输出结果：

Html代码  收藏代码
  1. [0] 123  
  2. [1] 124  
  3. [2] 125  
  4. [3] 126  
  5. [4] 134  
  6. [5] 135  
  7. [6] 136  
  8. [7] 145  
  9. [8] 146  
  10. [9] 156  
  11. [10] 234  
  12. [11] 235  
  13. [12] 236  
  14. [13] 245  
  15. [14] 246  
  16. [15] 256  
  17. [16] 345  
  18. [17] 346  
  19. [18] 356  
  20. [19] 456  

版权声明：本文为aademeng原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/aademeng/articles/7592104.html