Java组合算法（m个n选1） 博客分类： 算法

摘自：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。具体的组合如下：

 

[plain] view plaincopy

 

1. 01: a d f  
2. 02: a d g  
3. 03: a d h  
4. 04: a e f  
5. 05: a e g  
6. 06: a e h  
7. 07: b d f  
8. 08: b d g  
9. 09: b d h  
10. 10: b e f  
11. 11: b e g  
12. 12: b e h  
13. 13: c d f  
14. 14: c d g  
15. 15: c d h  
16. 16: c e f  
17. 17: c e g  
18. 18: c e h  

 

上面是纯数学、纯人工组合出来的，效率太低下了。如果使用Java语言进行编程，打印出这18组组合结果，又该如何实现呢？

二、循环迭代式的组合

可能很多程序员立马会想到，这个简单，不就三个数字（或List）吗，三个嵌套循环不就出来了！那么就来看看具体的实现。

 

[java] view plaincopy

 

1. @Test  
2. public void testCompositeUseIteration() {  
3.     List<String> listA = new ArrayList<String>();  
4.     listA.add("a");  
5.     listA.add("b");  
6.     listA.add("c");  
7.           
8.     List<String> listB = new ArrayList<String>();  
9.     listB.add("d");  
10.     listB.add("e");  
11.           
12.     List<String> listC = new ArrayList<String>();  
13.     listC.add("f");  
14.     listC.add("g");  
15.     listC.add("h");  
16.           
17.     int index = 0;  
18.     for (String itemA : listA) {  
19.         for (String itemB : listB) {  
20.             for (String itemC : listC) {  
21.                 index++;  
22.                 String str = index + ": \t" + itemA + " " + itemB + " " + itemC;  
23.                 System.out.println(str);  
24.             }  
25.         }  
26.     }  
27. }  

 

上面这段代码可以正确的打印出18种不重复的组合方式。

这种方法解决简单的m个n选1是没有任何问题的，但在实际应用中，m值并不是一直是3（m值即嵌套for循环的个数），有可能会更大，甚至m值会经常变化，比如m=10或m=20，难道就要写10个或20个for嵌套循环吗？显然，for嵌套循环方法肯定不能满足实现应用的需求，更为致命的是，当m值发生变化时，必须要修改代码，然后重新编译、发布，针对已经上线的生产系统，这也是不允许的。

三、可变组数的高级迭代组合

再来分析下前面的18组组合结果，其实是有规律可循的。

首先是要算出总的组合种数，这个很容易；然后按照从左到右、不重复的组合原则，就会得到一个元素迭代更换频率，这个数很重要，从左至右，每组的迭代更换频率是不一样的，但同组里的每个元素的迭代更换频率是一样的。

说实话，用文字来描述这个规律还真是有些困难，我在纸上画了画，就看图来领会吧！

找到了规律，那么写代码就不是问题了，具体实现如下（有兴趣的朋友可以将关键代码封装成方法，传入一个List<List<E>>的参数即可返回组合结果）：

 

[java] view plaincopy

 

1. /** 
2. * 组合记号辅助类 
3. * @author xht555 
4.  * @Create 2015-1-29 17:14:12 
5.  */  
6. private class Sign {  
7.     /** 
8.      * 每组元素更换频率，即迭代多少次换下一个元素 */  
9.     public int whenChg;  
10.     /** 
11.      * 每组元素的元素索引位置 */  
12.     public int index;  
13. }  
14.   
15. @Test  
16. public void testComposite(){  
17.     List<String> listA = new ArrayList<String>();  
18.     listA.add("a");  
19.     listA.add("b");  
20.     listA.add("c");  
21.       
22.     List<String> listB = new ArrayList<String>();  
23.     listB.add("d");  
24.     listB.add("e");  
25.       
26.     List<String> listC = new ArrayList<String>();  
27.     listC.add("f");  
28.     listC.add("g");  
29.     listC.add("h");  
30.       
31.     // 这个list可以任意扩展多个  
32.     List<List<String>> list = new ArrayList<List<String>>();  
33.     list.add(listA);    // 3  
34.     list.add(listB);    // 2  
35.     list.add(listC);    // 3  
36.     //list.add(listD);  
37.     //list.add(listE);  
38.     //list.add(listF);  
39.       
40.     int iterateSize = 1;// 总迭代次数，即组合总种数  
41.     for (int i = 0; i < list.size(); i++) {  
42.         // 每个List的n选1选法种数  
43.         // 有兴趣的话可以扩展n选2，n选3，... n选x  
44.         iterateSize *= list.get(i).size();  
45.     }  
46.       
47.     int median = 1; // 当前元素与左边已定元素的组合种数  
48.     Map<Integer, Sign> indexMap = new HashMap<Integer, Sign>();  
49.     for (int i = 0; i < list.size(); i++) {  
50.         median *= list.get(i).size();  
51.         Sign sign = new Sign();  
52.         sign.index = 0;  
53.         sign.whenChg = iterateSize/median;  
54.         indexMap.put(i, sign);  
55.     }  
56.       
57.     System.out.println("条目总数: " + iterateSize);  
58.     Set<String> sets = new HashSet<String>();  
59.       
60.     int i = 1;  // 组合编号  
61.           
62.     long t1 = System.currentTimeMillis();  
63.     while (i <= iterateSize) {  
64.         String s = "i: " + i + "\t";  
65.           
66.         // m值可变  
67.         for (int m = 0; m < list.size(); m++) {  
68.             int whenChg = indexMap.get(m).whenChg;  // 组元素更换频率  
69.             int index = indexMap.get(m).index;      // 组元素索引位置  
70.   
71.             s += list.get(m).get(index) + "[" + m + "," + index + "]" + " ";  
72.               
73.             if (i%whenChg == 0) {  
74.                 index++;  
75.                 // 该组中的元素组合完了，按照元素索引顺序重新取出再组合  
76.                 if (index >= list.get(m).size()) {  
77.                     index = 0;  
78.                 }  
79.                       
80.                 indexMap.get(m).index = index;  
81.             }  
82.         }  
83.               
84.         System.out.println(s);  
85.         sets.add(s);  
86.         i++;  
87.     }  
88.       
89.     System.out.println("Set条目总数: " + sets.size());  
90.     long t2 = System.currentTimeMillis();  
91.     System.err.println(String.format("%s ms", t2 - t1));  
92. }  

 

运行结果如下：

 

[plain] view plaincopy

 

1. 条目总数: 18  
2. i: 1    a[0,0] d[1,0] f[2,0]   
3. i: 2    a[0,0] d[1,0] g[2,1]   
4. i: 3    a[0,0] d[1,0] h[2,2]   
5. i: 4    a[0,0] e[1,1] f[2,0]   
6. i: 5    a[0,0] e[1,1] g[2,1]   
7. i: 6    a[0,0] e[1,1] h[2,2]   
8. i: 7    b[0,1] d[1,0] f[2,0]   
9. i: 8    b[0,1] d[1,0] g[2,1]   
10. i: 9    b[0,1] d[1,0] h[2,2]   
11. i: 10   b[0,1] e[1,1] f[2,0]   
12. i: 11   b[0,1] e[1,1] g[2,1]   
13. i: 12   b[0,1] e[1,1] h[2,2]   
14. i: 13   c[0,2] d[1,0] f[2,0]   
15. i: 14   c[0,2] d[1,0] g[2,1]   
16. i: 15   c[0,2] d[1,0] h[2,2]   
17. i: 16   c[0,2] e[1,1] f[2,0]   
18. i: 17   c[0,2] e[1,1] g[2,1]   
19. i: 18   c[0,2] e[1,1] h[2,2]   
20. Set条目总数: 18  
21. 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