コンビネーション数を計算して出力

質問の説明:データのセットの組合せ数を計算し、出力します.

   ：  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