快捷導(dǎo)航

Java實(shí)現(xiàn)排列組合算法的兩種方案

更新時(shí)間：2024年04月23日 11:18:27 作者：月色無痕

Java排列組合算法是一種用于生成所有可能的排列和組合的算法,在Java中,可以使用遞歸或迭代的方式實(shí)現(xiàn)排列組合算法,本文給大家介紹了Java實(shí)現(xiàn)排列組合算法的兩種方案,需要的朋友可以參考下

假設(shè)現(xiàn)有 M=4 個(gè)數(shù)據(jù) a，b，c，d。從中隨機(jī)抽取n個(gè)數(shù)，n為1—4個(gè)數(shù)據(jù)進(jìn)行組合。那么數(shù)學(xué)中的計(jì)算組合方式為C(4,1) + C(4,2) + C(4,3) + C(4,4) = 4 + 6 + 4 + 1 = 15。那么共有15種組合方式。

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

我的做法是，按順序循環(huán)組合，數(shù)據(jù)分為已組合的數(shù)據(jù)和未組合（未組合數(shù)據(jù)指的是已組合數(shù)據(jù)往后剩余的數(shù)據(jù)），然后把未參與組合的進(jìn)行循環(huán)與已組合再次組合，循環(huán)進(jìn)行，直到最后。

如下示例，規(guī)律

已組合數(shù)據(jù) 剩余未參與組合的數(shù)據(jù)

1 a b,c,d //a 后面還有b,c,d未參與
2 b c,d //b 后面還有c,d未參與
3 c d //c 后面還有d未參與
4 d //d后面沒有了其他數(shù)據(jù)
//開始把上述第1行a — b,c,d 進(jìn)行二次循環(huán)組合
5 a,b c,d //a,b 后面還有c,d未參與
6 a,c d //a,c 后面還有d未參與
7 a,d
//開始把上面第5行a,b — c,d 行進(jìn)行循環(huán)組合
8 a,b,c d //a,b,c 后面還有d未參與
9 a,b,c,d
//開始把上面第2行b — c,d 行進(jìn)行循環(huán)組合
10 b,c d //b,c 后面還有c,d未參與
11 b,d
//開始把上面第3行c — d 行進(jìn)行循環(huán)組合
12 c,d
//開始把上面第6行a,c — d 行進(jìn)行循環(huán)組合
13 a,c,d
//開始把上面第8行a,b,c — d 行進(jìn)行循環(huán)組合
14 a,b,c,d
//開始把上面第10行b,c — d 行進(jìn)行循環(huán)組合
15 b,c,d
..............................依據(jù)上述規(guī)則，循環(huán)把每一行未組合的與當(dāng)前已組合的再次進(jìn)行組合，然后計(jì)算剩余未組合數(shù)據(jù)。至到未參與組合的數(shù)據(jù)個(gè)數(shù)為0

上述思路基本明了，按順序依次組合，只是根據(jù)每行上的未參與組合數(shù)據(jù)，進(jìn)行再次組合直到全部組合完成。代碼實(shí)現(xiàn)如下：

public static void main(String[] args) {
        //結(jié)果集
        List<String> resList = new ArrayList<>();
        //初始化需要組合的數(shù)據(jù)
        String[] arr = new String[]{"a","b","c","d"};
        List<String> initList = new LinkedList(Arrays.asList(arr));
        //map中 key:組合數(shù)據(jù)的前綴，value:未參與組合的數(shù)據(jù)
        Map<String,List<String>> map = new HashMap<>();
        for (int i = 0; i < initList.size(); i++) {
            String pj = initList.get(i);
            resList.add(pj);
            System.out.println(pj);
            //當(dāng)剩余未組合的數(shù)據(jù)個(gè)數(shù)為0時(shí) 不再繼續(xù)添加
            if(i+1 < initList.size()){
                //按順序排列 下標(biāo)為i后面未參與組合的數(shù)據(jù)
                List<String> syList = initList.subList(i+1,initList.size());
                map.put(pj,syList);
            }
        }
        combinLoop(map,resList);
        System.out.println(resList.size());
    }
 
    public static void combinLoop(Map<String,List<String>> map,List<String> resList){
        for (Map.Entry<String, List<String>> entry : map.entrySet()) {
            String prefix = entry.getKey();
            List<String> list = entry.getValue();
            Map<String,List<String>> map2 = new HashMap<>();
            //循環(huán)未參與組合的數(shù)據(jù)，與之前的prefix進(jìn)行組合
            for (int i = 0; i < list.size(); i++) {
                String newPre = prefix+list.get(i);
                System.out.println(newPre);
                resList.add(newPre);
                if(i+1 < list.size()){
                    //按順序排列,下標(biāo)為i后面未參與組合的數(shù)據(jù)集合
                    List<String> syList = list.subList(i+1,list.size());
                    map2.put(newPre,syList);
                }
            }
            combinLoop(map2,resList);
        }
    }

方案二：效率更快

此方法，對(duì)初始化數(shù)據(jù)initList進(jìn)行循環(huán)，把前一次的結(jié)果resultList與當(dāng)前參與循環(huán)的數(shù)據(jù)進(jìn)行一一組合，得到新的結(jié)果加入到已有的組合結(jié)果resultList中，initList依次循環(huán)，resultList不斷加入新的數(shù)據(jù)，重復(fù)進(jìn)行直到最后。如下示例：

對(duì)initList = {"a","b","c","d"} 進(jìn)行循環(huán)，初始化resultList為空。

當(dāng)前參與循環(huán)數(shù)據(jù) 前一次resultList集結(jié)束resultList集

第一次循環(huán) a null a
第二次循環(huán) b a a,b,ab
第三次循環(huán) c a,b,ab a,b,ab,c,ac,bc,abc
第四次循環(huán) d a,b,ab,c,ac,bc,abc a,b,ab,c,ac,bc,abc,d,ad,bd,abd,cd,acd,bcd,abcd

通過上述規(guī)律可看出，當(dāng)前參與循環(huán)的數(shù)據(jù)與已有的resultList集進(jìn)行新的組合，可得到黃色部分組合后的結(jié)果，再加上resultList中原來已有的數(shù)據(jù)，組成新的resultList與下一次參與循環(huán)的數(shù)據(jù)組合，依次進(jìn)行直到所有數(shù)據(jù)循環(huán)完成。

代碼如下：

    public static void combine2(){
        String[] arr = new String[]{"a","b","c","d"};
        //初始化數(shù)據(jù)
        List<String> initList = Arrays.asList(arr);
        //結(jié)果集
        List<String> resultList = new ArrayList<>();
        for (String init : initList) {
            //重新賦值上次循環(huán)組合后得到的resultList結(jié)果集
            List<String> list = new ArrayList<>(resultList);
            //resultList添加初始數(shù)據(jù)
            resultList.add(init);
            for (String pr : list) {
                //把前一次得到的resultList 與當(dāng)前數(shù)據(jù)重新進(jìn)行組合
                resultList.add(pr + init);
            }
        }
    }

到此這篇關(guān)于Java實(shí)現(xiàn)排列組合算法的兩種方案的文章就介紹到這了,更多相關(guān)Java排列組合算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: