摘自:http://blog.csdn.net/xht555/article/details/43278807
一、模型:
① 现有8个小球,对小球进行编号,依次为a、b、c、……、g、h。
② 将编号后的8个小球分成三组,分组情况如下:
■ 第一组:[a, b, c]
■ 第二组:[d, e]
■ 第三组:[f, g, h]
③ 从每组中选出一个小球,对选出的三个小球进行组合
问题:问一个有多少种不重复的组合方式,并列出详细的组合方式。
以上是一个典型的数学组合问题,因为是从每组中选出一个小球,所以每组的选法就有组元素个数种选法,所以组合种数应为18=3×2×3。具体的组合如下:
- 01: a d f
- 02: a d g
- 03: a d h
- 04: a e f
- 05: a e g
- 06: a e h
- 07: b d f
- 08: b d g
- 09: b d h
- 10: b e f
- 11: b e g
- 12: b e h
- 13: c d f
- 14: c d g
- 15: c d h
- 16: c e f
- 17: c e g
- 18: c e h
上面是纯数学、纯人工组合出来的,效率太低下了。如果使用Java语言进行编程,打印出这18组组合结果,又该如何实现呢?
二、循环迭代式的组合
可能很多程序员立马会想到,这个简单,不就三个数字(或List)吗,三个嵌套循环不就出来了!那么就来看看具体的实现。
- @Test
- public void testCompositeUseIteration() {
- List<String> listA = new ArrayList<String>();
- listA.add("a");
- listA.add("b");
- listA.add("c");
- List<String> listB = new ArrayList<String>();
- listB.add("d");
- listB.add("e");
- List<String> listC = new ArrayList<String>();
- listC.add("f");
- listC.add("g");
- listC.add("h");
- int index = 0;
- for (String itemA : listA) {
- for (String itemB : listB) {
- for (String itemC : listC) {
- index++;
- String str = index + ": \t" + itemA + " " + itemB + " " + itemC;
- System.out.println(str);
- }
- }
- }
- }
上面这段代码可以正确的打印出18种不重复的组合方式。
这种方法解决简单的m个n选1是没有任何问题的,但在实际应用中,m值并不是一直是3(m值即嵌套for循环的个数),有可能会更大,甚至m值会经常变化,比如m=10或m=20,难道就要写10个或20个for嵌套循环吗?显然,for嵌套循环方法肯定不能满足实现应用的需求,更为致命的是,当m值发生变化时,必须要修改代码,然后重新编译、发布,针对已经上线的生产系统,这也是不允许的。
三、可变组数的高级迭代组合
再来分析下前面的18组组合结果,其实是有规律可循的。
首先是要算出总的组合种数,这个很容易;然后按照从左到右、不重复的组合原则,就会得到一个元素迭代更换频率,这个数很重要,从左至右,每组的迭代更换频率是不一样的,但同组里的每个元素的迭代更换频率是一样的。
说实话,用文字来描述这个规律还真是有些困难,我在纸上画了画,就看图来领会吧!
找到了规律,那么写代码就不是问题了,具体实现如下(有兴趣的朋友可以将关键代码封装成方法,传入一个List<List<E>>的参数即可返回组合结果):
- /**
- * 组合记号辅助类
- * @author xht555
- * @Create 2015-1-29 17:14:12
- */
- private class Sign {
- /**
- * 每组元素更换频率,即迭代多少次换下一个元素 */
- public int whenChg;
- /**
- * 每组元素的元素索引位置 */
- public int index;
- }
- @Test
- public void testComposite(){
- List<String> listA = new ArrayList<String>();
- listA.add("a");
- listA.add("b");
- listA.add("c");
- List<String> listB = new ArrayList<String>();
- listB.add("d");
- listB.add("e");
- List<String> listC = new ArrayList<String>();
- listC.add("f");
- listC.add("g");
- listC.add("h");
- // 这个list可以任意扩展多个
- List<List<String>> list = new ArrayList<List<String>>();
- list.add(listA); // 3
- list.add(listB); // 2
- list.add(listC); // 3
- //list.add(listD);
- //list.add(listE);
- //list.add(listF);
- int iterateSize = 1;// 总迭代次数,即组合总种数
- for (int i = 0; i < list.size(); i++) {
- // 每个List的n选1选法种数
- // 有兴趣的话可以扩展n选2,n选3,... n选x
- iterateSize *= list.get(i).size();
- }
- int median = 1; // 当前元素与左边已定元素的组合种数
- Map<Integer, Sign> indexMap = new HashMap<Integer, Sign>();
- for (int i = 0; i < list.size(); i++) {
- median *= list.get(i).size();
- Sign sign = new Sign();
- sign.index = 0;
- sign.whenChg = iterateSize/median;
- indexMap.put(i, sign);
- }
- System.out.println("条目总数: " + iterateSize);
- Set<String> sets = new HashSet<String>();
- int i = 1; // 组合编号
- long t1 = System.currentTimeMillis();
- while (i <= iterateSize) {
- String s = "i: " + i + "\t";
- // m值可变
- for (int m = 0; m < list.size(); m++) {
- int whenChg = indexMap.get(m).whenChg; // 组元素更换频率
- int index = indexMap.get(m).index; // 组元素索引位置
- s += list.get(m).get(index) + "[" + m + "," + index + "]" + " ";
- if (i%whenChg == 0) {
- index++;
- // 该组中的元素组合完了,按照元素索引顺序重新取出再组合
- if (index >= list.get(m).size()) {
- index = 0;
- }
- indexMap.get(m).index = index;
- }
- }
- System.out.println(s);
- sets.add(s);
- i++;
- }
- System.out.println("Set条目总数: " + sets.size());
- long t2 = System.currentTimeMillis();
- System.err.println(String.format("%s ms", t2 - t1));
- }
运行结果如下:
- 条目总数: 18
- i: 1 a[0,0] d[1,0] f[2,0]
- i: 2 a[0,0] d[1,0] g[2,1]
- i: 3 a[0,0] d[1,0] h[2,2]
- i: 4 a[0,0] e[1,1] f[2,0]
- i: 5 a[0,0] e[1,1] g[2,1]
- i: 6 a[0,0] e[1,1] h[2,2]
- i: 7 b[0,1] d[1,0] f[2,0]
- i: 8 b[0,1] d[1,0] g[2,1]
- i: 9 b[0,1] d[1,0] h[2,2]
- i: 10 b[0,1] e[1,1] f[2,0]
- i: 11 b[0,1] e[1,1] g[2,1]
- i: 12 b[0,1] e[1,1] h[2,2]
- i: 13 c[0,2] d[1,0] f[2,0]
- i: 14 c[0,2] d[1,0] g[2,1]
- i: 15 c[0,2] d[1,0] h[2,2]
- i: 16 c[0,2] e[1,1] f[2,0]
- i: 17 c[0,2] e[1,1] g[2,1]
- i: 18 c[0,2] e[1,1] h[2,2]
- Set条目总数: 18
- 3 ms
四、兴趣扩展
有兴趣的朋友可以做下述尝试:
① m个n选x的组合实现;
② m个n选1的排列实现(先组后排);
排列会关注元素所在的位置(顺序),例如,三个元素“a d f”的排列大概如下:
■ a d f
■ a f d
■ d a f
■ d f a
■ f a d
■ f d a
相关推荐
排列组合 排列 组合 java排列组合算法 排列组合算法
该代码实现功能为数学中的C(n,m),n为下标,m为上标。
输出一个C(m,n)组合的所有结果 - VC-MFC - 图形处理-算法
java求组合数算法-从M个数中取出N个数
m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良的选择排序 快速排序法(一) 快速...
• m元素集合的n个元素子集 • 数字拆解 排序 • 得分排行 • 选择、插入、气泡排序 • Shell 排序法 - 改良的插入排序 • Shaker 排序法 - 改良的气泡排序 • Heap 排序法 - 改良的选择排序 • 快速排序法...
m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良的选择排序 快速排序法(一) 快速排序法(二...
(1) 用固定长度的染色体表示问题变量域,选择染色体种群数量为N,交叉概率为C,突变概率为M (2) 定义适应性函数来衡量问题域上单个染色体的性能或适应性。适应性函数是在繁殖过程中选择配对染色体的基础。 (3)...
m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良的选择排序 快速排序法(一) 快速排序法(二...
m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良的选择排序 快速排序法(一) 快速排序法(二...
算法 ['ælgәriðm] Annotation [java] 代码注释 [ænәu'teiʃәn] anonymous adj.匿名的[ә'nɒnimәs]'(反义:directly adv.直接地,立即[di'rektli, dai'rektli]) apply v.应用,适用 [ә'plai] application ...
m元素集合的n个元素子集 数字拆解 排序 得分排行 选择、插入、气泡排序 Shell 排序法 - 改良的插入排序 Shaker 排序法 - 改良的气泡排序 Heap 排序法 - 改良的选择排序 快速排序法(一) 快速排序法(二...
从1–9中选取N个数字,组成不重复的N位数,从小到大进行编号,当输入其中任何一个数M时,能找出该数字对应 的编号。如 N=3,M=213. 输出:[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)]—>X=2 首先...
具体题目是这样的: 从1–9中选取N个数字,组成不重复的N位数,从小到大进行编号,当输入其中任何一个数M时,能找出该数字对应 的编号。如 N=3,M=213. 输出:[123(1) , 132(2) , 213(3) , 231(4) , 312(5) , 321(6)...
Java Bean 是可复用的组件,对Java Bean并没有严格的规范,理论上讲,任何一个Java类都可以是一个Bean。但通常情况下,由于Java Bean是被容器所创建(如Tomcat)的,所以Java Bean应具有一个无参的构造器,另外,...
两个有序数组合并为一个有序数组 Java 实现 : 空间复杂度 O(1);时间复杂度 最好 O(m + n) 最坏 O(mn) 空间复杂度 O(m);时间复杂度 O(m + n) LeetCode#999 链表 单链表 Java实现 及 实现了链表的反转 双向链表 ...
Java Bean 是可复用的组件,对Java Bean并没有严格的规范,理论上讲,任何一个Java类都可以是一个Bean。但通常情况下,由于Java Bean是被容器所创建(如Tomcat)的,所以Java Bean应具有一个无参的构造器,另外,...
演算法数据结构数学数论组合学代数几何可能性线性代数基础Java 介绍弦乐大数数据结构异常处理高级暖身# 标题解时间空间困难点数注意 O(1) O(1) 简单1个 上) O(1) 简单10 O(1) O(1) 简单10 上) O(1) ...
1.NIM博弈 (n堆每次最少取一个) 2.威佐夫博弈(两堆每次取至少一个或一起取一样的) 3.约瑟夫环 4.斐波那契博弈 (取的数依赖于对手刚才取的数) 5.sg函数 数论: 1.数论 素数检验:普通素数判别 线性筛 二次筛法求素数 ...
需求寻呼米格尔·阿米戈特操作系统,2014 年秋季RANDOM、FIFO、LRU需求分页... N,每个过程的引用数。 R,替换算法,FIFO、RANDOM 或 LRU。编译在包含 DemandPaging.java、Process.java、Frame.java 和 JobMixProbabili