`
ai_zxc
  • 浏览: 11910 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

双色球33选6红球 排列组合算法 C(33,6) - 咋个办呢

阅读更多

今天同学问我一个问题,计算出来双色球33选6个红球排列组合所有的组合,要求最小化算法时间。

1,23,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33

排列组合后总共有1107568中情况(1107568 = 33!/(33-6)!*6!)

下面java代码为计算所有情况算法,去掉IO后,耗时15ms。

 

其中算法核心为:最小组合(1,2,3,4,5,6) , 最大组合(28,29,30,31,32,33), 每一组组合规律为 (A<B<C<D<E<F) 。

 

package c;
 
import java.io.FileNotFoundException;
 
/**
 * 排列组合
 * @author 咋个办呢
 */
public class PermutationsCombinations {
 
    /**
     * 递归算法核心
     * @param pce
     * @param w
     * @param m
     */
    private static void calpce(int[] pce , int w , int m){
        if(pce[w]+1>(m-pce.length+w+1)){
            if(w>0){
                calpce(pce, w-1, m) ;
                pce[w] = pce[w-1]+1 ;
            }
            else{
                pce[w] = pce[w]+1 ;
            }
        }
        else{
            pce[w] = pce[w]+1 ;
        }
    }
 
    private static int sumCount(int m , int n){
        int a=1 ,c=1 ;
        for(int _m=m ; _m>(m-n) ; _m-- ){
            a = a * _m ;
        }
        for(int _n=n ; _n>0 ; _n--){
            c = c*_n ;
        }
        return a/c ;
    }
 
    public static void main(String[] args) throws FileNotFoundException {
 
        int[] pces = new int[33] ;
 
        for(int i=0 ; i<pces.length ; i++){
            pces[i] = i + 1 ;
            if(i%11==0){
                System.out.println();
            }
            System.out.print(pces[i]+",");
        }
		
        System.out.println();
 
        int sumc = sumCount(33, 6) ;
		
        System.out.println("排列组合后共有"+sumc+"个组合。");
 
        int[] pce = new int[]{1,2,3,4,5,6} ;
 
        int count = 0 ;
		
        long t1 = System.currentTimeMillis() ;
        while(count<=sumc){
            count++ ;
//          System.out.println(String.format("[%d,%d,%d,%d,%d,%d]",pce[0],pce[1],pce[2],pce[3],pce[4],pce[5]));
            calpce(pce, 6-1, 33);
        }
        long t2 = System.currentTimeMillis() ;
		
        System.out.println("耗时:"+(t2-t1)+"ms,计数总数:"+(count-1));
    }
 
}

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics