java实现排列组合算法

这篇具有很好参考价值的文章主要介绍了java实现排列组合算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

        假设现有 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<String> resList = new ArrayList<>();
        //初始化需要组合的数据
        String[] arr = new String[]{"a","b","c","d"};
        List<String> initList = new LinkedList(Arrays.asList(arr));
        //map中 key:组合数据的前缀,value:未参与组合的数据
        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);
            //当剩余未组合的数据个数为0时 不再继续添加
            if(i+1 < initList.size()){
                //按顺序排列 下标为i后面未参与组合的数据
                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<>();
            //循环未参与组合的数据,与之前的prefix进行组合
            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()){
                    //按顺序排列,下标为i后面未参与组合的数据集合
                    List<String> syList = list.subList(i+1,list.size());
                    map2.put(newPre,syList);
                }
            }
            combinLoop(map2,resList);
        }
    }

方案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与下一次参与循环的数据组合,依次进行直到所有数据循环完成。

代码如下:文章来源地址https://www.toymoban.com/news/detail-548910.html

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

到了这里,关于java实现排列组合算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】用Java实现七大排序算法

    目录 🌷1. 排序的概念及引用 1.1 排序的概念 1.2 衡量指标 1.2 十个排序算法  1.3 十个排序性能对比 🌷2. 冒泡排序 2.1 算法描述 2.2 动图 ⭐️代码优化 🌷3. 选择排序 3.1 算法描述 3.2 动图  3.3 代码 🌷4. 插入排序 4.1 算法描述 4.2 动图  4.3 代码 🌷5 希尔排序 5.1 描述 5.2 动图  

    2023年04月23日
    浏览(49)
  • 【算法与数据结构】Java实现查找与排序

    也叫做折半查找,属于有序查找算法。 前提条件 :数组数据必须有序,从小到大,或者从大到小都是可以的。 如果是无序的,也可以先进行排序。 但是排序之后,会改变原有数据的顺序,查找出来元素位置跟原来的元素可能是不一样的,所以排序之后再查找只能判断当前数

    2024年01月19日
    浏览(46)
  • 【算法教程】排列与组合的实现

    在讲排列与组合之前,我们先定义数据元素类型Fruit 对N个不同元素进行排序,总共有多少不同的排列方式? 例子:某水果店有以下水果,请对所有水果进行全排列,请输出所有排列 排列算法的javascript实现模板(DSF,最优解in-place) 测试结果 对N个不同元素进行排序,总共有多少不

    2024年02月07日
    浏览(42)
  • 【一起学数据结构与算法】Java实现双链表

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 打印双链表非常简单,只需要单独创一个结点

    2024年02月22日
    浏览(42)
  • 【数据结构与算法】1、学习动态数组数据结构(基本模拟实现 Java 的 ArrayList 实现增删改查)

    🍃 数据结构是 计算机 存储 、 组织 数据的方式 🎉 线性 结构 线性表(数组、链表、栈、队列、哈希表) 🎉 树形 结构 二叉树 AVL 树 红黑树 B 树 堆 Trie 哈夫曼树 并查集 🎉 图形 结构 邻接矩阵 邻接表 🎁 线性表是具有 n 个 相同类型元素 的有限 序列 (n = 0) a1 是首节点

    2024年02月10日
    浏览(75)
  • 数据结构与算法中的七大排序(Java实现)

    目录 一、直接插入排序 二、希尔排序 三、直接选择排序 四、堆排序 五、冒泡排序 六、快速排序 七、归并排序               定义i下标之前的元素全部已经有序 ,遍历一遍要排序的数组,把i下标前的元素全部进行排序,当遍历玩这个数组后,就已经排好序了。        

    2024年02月06日
    浏览(55)
  • 深入理解Java线程池ThreadPoolExcutor实现原理、数据结构和算法(源码解析)

    什么是线程池?         线程池主要是为了解决执行新任务执行时,应用程序为减少为任务创建一个新线程和任务执行完毕时销毁线程所带来的开销。通过线程池,可以在项目初始化时就创建一个线程集合,然后在需要执行新任务时重用这些线程而不是每次都新建一个线

    2024年02月07日
    浏览(45)
  • 数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。

    最短路径的算法有两个, Dijkstra算法 和 Floyd算法 。 Dijkstra算法 解决的是 单源 最短路径问题 。 Floyd算法解决的是 多源 最短路径问题,并且可以处理负权图 。 今天要讲的就是Dijkstra算法。 加: feng--Insist (大写的i),进java交流群讨论互联网+技术。可索要PPT等资料。 其他资料

    2024年02月11日
    浏览(51)
  • 数据结构:树和二叉树之-堆排列 (万字详解)

    目录 树概念及结构 1.1树的概念 1.2树的表示 ​编辑2.二叉树概念及结构 2.1概念 2.2数据结构中的二叉树:​编辑 2.3特殊的二叉树: ​编辑 2.4 二叉树的存储结构 2.4.1 顺序存储: 2.4.2 链式存储: 二叉树的实现及大小堆排列 1功能展示 2 定义基本结构 3 初始化 4打印 5销毁 6插入

    2024年02月07日
    浏览(39)
  • java入门,程序=数据结构+算法

    一、前言 在学习java的时候,我印象最深的一句话是:程序=数据结构+算法,对于写java程序来说,这就是java的入门。 二、java基本数据结构与算法 1、数据类型 java中的数据类型8种基本数据类型: 整型 byte 、short 、int 、long 浮点型 float 、 double 字符型 char 布尔型 boolean 还有包

    2024年02月05日
    浏览(59)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包