计算组合数并输出

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

 例如：输入1,2,3,4,5时，大小取3，共有C(5,3)=10个组合数，
 将其从小到大依次排序可分组如下：
 ----
 123 
 124
 125
 134
 135
 145
 ----
 234
 235
 245
 ----
 345
 解题思路：求长度为 n 的source[]数组，且大小为 m 的第 x 个组合数
 1)获取组合数的第一个字符
   因为 C(n,m) = C(n-1,m-1) + C(n-2,m-1) + .. + C(m-1,m-1)
   所以可依次计算 C(n-k,m-1) [1 <= k <= n-m+1]的值，直到
   x < C(n-1,m-1) + C(n-2,m-1) + .. + C(n-k,m-1)
   这时 source[k-1] 就是组合数的第一个字符
 2)获取下一个字符
   在获取了第一个字符之后，记 
   y = x - (C(n-1,m-1) + C(n-2,m-1) + .. + C(n-k+1,m-1))
   问题降级为在起始下标为 k,长度为 n-k 的source[]数组中,
   选择大小为 --m 的第 y 个组合数，因此可重复1)的过程
 3)当 m == 1时，选取组合数的最后一个字符，完成运算
   

 

package org.demo.algorithm;
/**
 * 计算并输出组合数
 * @author  
 * @date    2010-9-13
 * @file    org.demo.algorithm.Combination.java
 */
public class Combination {
	/**
	 * 测试
	 * @param args
	 */
	public static void main(String[] args) {
		String[] source = {"1","2","3","4","5","6"};
		int m = 3;
		int size = (int)getCnm(source.length,m);
		for (int i=0; i<size; i++){
			String data = getValue(source,m,i);
			System.out.println("[" + i + "] " + data);
		}
	}
	/**
	 * 计算数组 source[] 中大小为 m 的第 x 个组合数
	 * 按下述原理分组
	 * C(n,m) = C(n-1,m-1) + C(n-1,m)
	 * C(n,m) = C(n-1,m-1) + C(n-2,m-1) + C(n-2,m)
	 * ...
	 * C(n,m) = C(n-1,m-1) + C(n-2,m-1) + .. + C(m,m-1) + C(m,m)
	 * C(n,m) = C(n-1,m-1) + C(n-2,m-1) + .. + C(m,m-1) + C(m-1,m-1)
	 * 最后一步转换是因为 C(m,m) == C(m-1,m-1)
	 * @param source
	 * @param m 组合数的大小，且 1 <= m <= source.length
	 * @param x [0,C(n,m))
	 * @return
	 */
	public static String getValue(String[] source,int m,int x){
		// 数组大小
		int n = source.length;
		// 存储组合数
		StringBuilder sb = new StringBuilder();
		int start = 0;
		while(m > 0){
			if (m == 1){
				// m == 1 时为组合数的最后一个字符
				sb.append(source[start + x]);
				break;
			}
			for (int i=0; i<=n-m; i++){						
				int cnm =  (int)getCnm(n-1-i,m-1);
				if(x <= cnm-1){
					sb.append(source[start + i]);
					// 启始下标前移
					start = start + (i + 1);
					// 搜索区域减小
					n = n - (i+1);
					// 组合数的剩余字符个数减少
					m--;
					break;
				} else {
					x = x - cnm;					
				}		
			}
		}
		return sb.toString();
	}
	/**
	 * 计算组合数
	 * 计算组合数的推导过程如下，
	 * 因为直接计算 n! 容易发生数据溢出，故可改为计算 ln(n)
	 * C(n,m) = n!/(m!(n-m)!) 
	 * C(n,m) = n(n-1)..(n-m+1)/m!
	 * ln(C(n,m)) = ln(n(n-1)..(n-m+1)/m!)
	 * ln(C(n,m)) = ln(n(n-1)..(n-m+1)) - ln(m!)
	 * ln(C(n,m)) = (ln(n) + ln(n-1) + .. + ln(n-m+1))
	 *             -(ln(m) + ln(m-1) + .. + ln(1))
	 * 由上可知 C(n,m) = e^ln(C(n,m)),
	 * 并且由公式右侧可知，m 越小计算量越小
	 * ∵ C(n,m) = C(n,n-m)
	 * ∴ 当 m>n/2.0时,可改为计算 C(n,n-m)
	 * @param n
	 * @param m
	 * @return
	 */
	public static long getCnm(int n,int m){
		if (n < 0 || m < 0){
			throw new IllegalArgumentException("n,m must be > 0");
		}
		if (n == 0 || m == 0){
			return 1;
		}
		if (m > n){
			return 0;
		}
		if (m > n/2.0){
			m = n-m;
		}
		double result = 0.0;
		for (int i=n; i>=(n-m+1); i--){
			result += Math.log(i);
		}
		for (int i=m; i>=1; i--){
			result -= Math.log(i);
		}
		result = Math.exp(result);
		return Math.round(result);
	}
}

 

输出结果：

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

 

评论

1 楼 stanly7 2013-08-16  

组合数用log求然后再算回去，会有差错。在数字比较大的时候就会出错。