小工具知识网

当前位置: 首页 > 行业知识 > java实现排列组合算法

行业知识

java实现排列组合算法

2026-11-18 01:13:17 来源:互联网转载

���这里只写了组合的算法。

()

        假设现有 M=4 个数据 a,b,c,d。从中随机抽取n个数,n为1—4个数据进行组合。那么数学中的计算组合方式为C(4,1) + C(4,2) + C(4,3) + C(4,4)  = 4 + 6 + 4 + 1 = 15。那么共有15种组合方式。

方案一:此方法容易理解但是效率慢

        我的做法是,按顺序循环组合,数据分为已组合的数据和未组合(未组合数据指的是已组合数据往后剩余的数据),然后把未参与组合的进行循环与已组合再次组合,循环进行,直到最后。

()

        如下示例,规律

      已组合数据    剩余未参与组合的数据

1       a                            b,c,d               //a 后面还有b,c,d未参与
2       b                             c,d                 //b 后面还有c,d未参与
3       c                             d                   //c 后面还有d未参与
4       d                                                 //d后面没有了其他数据

//开始把上述第1行a —  b,c,d 进行二次循环组合
5       a,b                          c,d               //a,b 后面还有c,d未参与         
6       a,c                           d                 //a,c 后面还有d未参与          
7       a,d                                                                                                                                          

//开始把上面第5行a,b —  c,d 行进行循环组合      
8       a,b,c                        d                //a,b,c 后面还有d未参与
9       a,b,c,d

//开始把上面第2行b  —  c,d 行进行循环组合
10     b,c                          d                //b,c 后面还有c,d未参与
11     b,d                          

//开始把上面第3行c  —  d 行进行循环组合
12      c,d                                             

//开始把上面第6行a,c  —  d 行进行循环组合
13      a,c,d                                         

//开始把上面第8行a,b,c  —  d 行进行循环组合
14      a,b,c,d                                      

//开始把上面第10行b,c  —  d 行进行循环组合
15      b,c,d                                         
..............................依据上述规则,循环把每一行未组合的与当前已组合的再次进行组合,然后计算剩余未组合数据。至到未参与组合的数据个数为0

上述思路基本明了,按顺序依次组合,只是根据每行上的未参与组合数据,进行再次组合直到全部组合完成。代码实现如下:

public static void main(String[] args) {        //结果集        List resList = new ArrayList();        //初始化需要组合的数据        String[] arr = new String[]{"a","b","c","d"};        List initList = new LinkedList(Arrays.asList(arr));        //map中 key:组合数据的前缀,value:未参与组合的数据        Map map = new HashMap();        for (int i = 0; i  

方案2:效率更快

此方法,对初始化数据initList进行循环,把前一次的结果resultList与当前参与循环的数据进行一一组合,得到新的结果加入到已有的组合结果resultList中,initList依次循环,resultList不断加入新的数据,重复进行直到最后。如下示例:

对initList = {"a","b","c","d"} 进行循环,初始化resultList为空。

              当前参与循环数据   前一次resultList集    结束resultList集

第一次循环      a                        null                                    a

第二次循环      b                         a                                    a,b,ab

第三次循环      c                      a,b,ab                             a,b,ab,c,ac,bc,abc

第四次循环      d                a,b,ab,c,ac,bc,abc    a,b,ab,c,ac,bc,abc,d,ad,bd,abd,cd,acd,bcd,abcd   

通过上述规律可看出,当前参与循环的数据与已有的resultList集进行新的组合,可得到黄色部分组合后的结果,再加上resultList中原来已有的数据,组成新的resultList与下一次参与循环的数据组合,依次进行直到所有数据循环完成。

代码如下:

    public static void combine2(){        String[] arr = new String[]{"a","b","c","d"};        //初始化数据        List initList = Arrays.asList(arr);        //结果集        List resultList = new ArrayList();        for (String init : initList) {            //重新赋值上次循环组合后得到的resultList结果集            List list = new ArrayList(resultList);            //resultList添加初始数据            resultList.add(init);            for (String pr : list) {                //把前一次得到的resultList 与当前数据重新进行组合                resultList.add(pr + init);            }        }    }

上一篇:暴雪世界怎么换城市服务器?

下一篇:大勤揭秘,一网打尽核心亮点!