文档章节

高效率的排列组合算法(java实现)

梁金晶
 梁金晶
发布于 2016/10/10 16:12
字数 640
阅读 421
收藏 1
  1. package BeanUtil;
  2.  
  3. import java.util.ArrayList;
  4. import java.util.List;
  5.  
  6. import com.work.core.exception.OurException;
  7.  
  8. /**
  9.  * 统计任三出现的最多的几率的组合
  10.  * 
  11.  * @author wangmingjie
  12.  * @date 2009-1-1下午01:22:19
  13.  */
  14. public class Copy_2_of_StatisAnyThree {
  15. //  组合算法   
  16. //    本程序的思路是开一个数组,其下标表示1到m个数,数组元素的值为1表示其下标   
  17. //    代表的数被选中,为0则没选中。     
  18. //    首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。     
  19. //    然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为   
  20. //    “01”组合,同时将其左边的所有“1”全部移动到数组的最左端。     
  21. //    当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得   
  22. //    到了最后一个组合。     
  23. //    例如求5中选3的组合:     
  24. //    1   1   1   0   0   //1,2,3     
  25. //    1   1   0   1   0   //1,2,4     
  26. //    1   0   1   1   0   //1,3,4     
  27. //    0   1   1   1   0   //2,3,4     
  28. //    1   1   0   0   1   //1,2,5     
  29. //    1   0   1   0   1   //1,3,5     
  30. //    0   1   1   0   1   //2,3,5     
  31. //    1   0   0   1   1   //1,4,5     
  32. //    0   1   0   1   1   //2,4,5     
  33. //    0   0   1   1   1   //3,4,5   
  34.     public static void main(String[] args) {
  35.         Copy_2_of_StatisAnyThree s = new Copy_2_of_StatisAnyThree();
  36.         s.printAnyThree();      
  37.     }
  38.     
  39.     /**
  40.      * 
  41.      */
  42.     public void printAnyThree(){
  43.         int[] num = new int[]{1,2,3,4,5,6};
  44.         print(combine(num,3));
  45.     }
  46.  
  47.     /**
  48.      * 从n个数字中选择m个数字
  49.      * @param a
  50.      * @param m
  51.      * @return
  52.      */
  53.     public List combine(int[] a,int m){
  54.         int n = a.length;
  55.         if(m>n){
  56.             throw new OurException("错误!数组a中只有"+n+"个元素。"+m+"大于"+2+"!!!");
  57.         }
  58.         
  59.         List result = new ArrayList();
  60.         
  61.         int[] bs = new int[n];
  62.         for(int i=0;i<n;i++){
  63.             bs[i]=0;
  64.         }
  65.         //初始化
  66.         for(int i=0;i<m;i++){
  67.             bs[i]=1;
  68.         }
  69.         boolean flag = true;
  70.         boolean tempFlag = false;
  71.         int pos = 0;
  72.         int sum = 0;
  73.         //首先找到第一个10组合,然后变成01,同时将左边所有的1移动到数组的最左边
  74.         do{
  75.             sum = 0;
  76.             pos = 0;
  77.             tempFlag = true; 
  78.             result.add(print(bs,a,m));
  79.             
  80.             for(int i=0;i<n-1;i++){
  81.                 if(bs[i]==1 && bs[i+1]==0 ){
  82.                     bs[i]=0;
  83.                     bs[i+1]=1;
  84.                     pos = i;
  85.                     break;
  86.                 }
  87.             }
  88.             //将左边的1全部移动到数组的最左边
  89.             
  90.             for(int i=0;i<pos;i++){
  91.                 if(bs[i]==1){
  92.                     sum++;
  93.                 }
  94.             }
  95.             for(int i=0;i<pos;i++){
  96.                 if(i<sum){
  97.                     bs[i]=1;
  98.                 }else{
  99.                     bs[i]=0;
  100.                 }
  101.             }
  102.             
  103.             //检查是否所有的1都移动到了最右边
  104.             for(int i= n-m;i<n;i++){
  105.                 if(bs[i]==0){
  106.                     tempFlag = false;
  107.                     break;
  108.                 }
  109.             }
  110.             if(tempFlag==false){
  111.                 flag = true;
  112.             }else{
  113.                 flag = false;
  114.             }
  115.             
  116.         }while(flag);
  117.         result.add(print(bs,a,m));
  118.         
  119.         return result;
  120.     }
  121.     
  122.     private int[] print(int[] bs,int[] a,int m){
  123.         int[] result = new int[m];
  124.         int pos= 0;
  125.         for(int i=0;i<bs.length;i++){
  126.             if(bs[i]==1){
  127.                 result[pos]=a[i];
  128.                 pos++;
  129.             }
  130.         }
  131.         return result ;
  132.     }
  133.     
  134.     private void print(List l){
  135.         for(int i=0;i<l.size();i++){
  136.             int[] a = (int[])l.get(i);
  137.             for(int j=0;j<a.length;j++){
  138.                 System.out.print(a[j]+"/t");
  139.             }
  140.             System.out.println();
  141.         }
  142.     }
  143. }

© 著作权归作者所有

梁金晶
粉丝 6
博文 47
码字总数 131327
作品 1
黄浦
架构师
私信 提问
matlab数学计算!!!

可靠度的置信下限的计算: 公式的含义是 Int a=0; For( int k=0;k<=f;k++) { a=a+C(n,k)*(R的(n-k)次方)*((1-R)的k次方); } 注意其中C(n,k)表示从n取k的排列组合:C(n,k)=(k!)/(...

liuwanjie
2014/01/07
267
1
IKAnalyzer的网友评论

IKAnalyzer是一个开源的,基于java语言开发的轻量级的中文分词工具包。从2006年12月推出1.0版开始,IKAnalyzer已经推出 了3个大版本。最初,它是以开源项目Luence为应用主体的,结合词典分词...

红薯
2009/12/11
595
1
Java程序员进化为架构师需要掌握的知识

Java程序员进化为架构师掌握的知识: 一:Java知识 1、进制转换 2、Java基本数据类型 面向对象相关知识 3、类、接口、抽象类 this关键字、static关键字、final关键字 方法的参数传递机制 Ja...

andogo
2014/05/16
1K
2
算法设计:两种快速排序代码实现

快速排序是一种高效且使用广泛的排序算法,在很多语言的标准库中自带的排序都是快速排序,所以我们也有必要了解快排的原理以及其实现方法。 快排的大致思想 快速排序实现的重点在于数组的拆分...

Sunrise_1018
2018/11/23
0
0
关于 Java Collections API 您可能不知道的 5 件事

对于很多 Java 开发人员来说,Java Collections API 是标准 Java 数组及其所有缺点的一个非常需要的替代品。将 Collections 主要与 联系到一起本身没有错,但是对于那些有探索精神的人来说,...

红薯
2010/05/26
487
1

没有更多内容

加载失败,请刷新页面

加载更多

我为什么要写微信公众号

埋一颗种子,细心呵护,静待她枝繁叶茂,葱郁参天 V2论坛上有个帖子【做程序员最重要的还是一定要有自己的作品】,作者写道: 能有一个作品和你的名字联系在一起,应当成为在职业生涯前期着意...

运维咖啡吧
40分钟前
3
0
数据库

数据库架构 数据库架构可以分为存储文件系统和程序实例两大块,而程序实例根据不同的功能又可以分为如下小模块。 1550644570798 索引模块 常见的问题有: 为什么要使用索引 什么样的信息能成...

一只小青蛙
今天
5
0
PHP常用经典算法实现

<? //-------------------- // 基本数据结构算法 //-------------------- //二分查找(数组里查找某个元素) function bin_sch($array, $low, $high, $k){ if ( $low <= $high){ $mid = int......

半缘修道半缘君丶
昨天
5
0
GIL 已经被杀死了么?

本文原创并首发于公众号【Python猫】,未经授权,请勿转载。 原文地址:https://mp.weixin.qq.com/s/8KvQemz0SWq2hw-2aBPv2Q 花下猫语: Python 中最广为人诟病的一点,大概就是它的 GIL 了。...

豌豆花下猫
昨天
6
0
git commit message form

commit message一般包括3部分:Header、Body、Footer。 <type>(<scope>):<subject>blank line<body>blank line<footer> header是必需的,body、footer可以省略。 header中type、subject......

ninjaFrog
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部