java 算法 n_[转]Java组合算法（m个n选1）

港控/mmm° 2022-11-03 05:48 175阅读 0赞

http://www.codes51.com/article/detail\_109971.html

一、模型：

①    现有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 listA = new ArrayList();

listA.add("a");

listA.add("b");

listA.add("c");

List listB = new ArrayList();

listB.add("d");

listB.add("e");

List listC = new ArrayList();

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组组合结果，其实是有规律可循的。

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

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

![21086a7026c92bfd7240ae238563fcc2.png][]

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

/\*\*

\* 组合记号辅助类

\* @author xht555

\* @Create 2015-1-29 17:14:12

\*/

private class Sign \{

/\*\*

\* 每组元素更换频率，即迭代多少次换下一个元素 \*/

public int whenChg;

/\*\*

\* 每组元素的元素索引位置 \*/

public int index;

@Test

public void testComposite()\{

List listA = new ArrayList();

listA.add("a");

listA.add("b");

listA.add("c");

List listB = new ArrayList();

listB.add("d");

listB.add("e");

List listC = new ArrayList();

listC.add("f");

listC.add("g");

listC.add("h");

// 这个list可以任意扩展多个

List> list = new ArrayList>();

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 indexMap = new HashMap();

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 sets = new HashSet();

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: 1a\[0,0\] d\[1,0\] f\[2,0\]

i: 2a\[0,0\] d\[1,0\] g\[2,1\]

i: 3a\[0,0\] d\[1,0\] h\[2,2\]

i: 4a\[0,0\] e\[1,1\] f\[2,0\]

i: 5a\[0,0\] e\[1,1\] g\[2,1\]

i: 6a\[0,0\] e\[1,1\] h\[2,2\]

i: 7b\[0,1\] d\[1,0\] f\[2,0\]

i: 8b\[0,1\] d\[1,0\] g\[2,1\]

i: 9b\[0,1\] d\[1,0\] h\[2,2\]

i: 10b\[0,1\] e\[1,1\] f\[2,0\]

i: 11b\[0,1\] e\[1,1\] g\[2,1\]

i: 12b\[0,1\] e\[1,1\] h\[2,2\]

i: 13c\[0,2\] d\[1,0\] f\[2,0\]

i: 14c\[0,2\] d\[1,0\] g\[2,1\]

i: 15c\[0,2\] d\[1,0\] h\[2,2\]

i: 16c\[0,2\] e\[1,1\] f\[2,0\]

i: 17c\[0,2\] e\[1,1\] g\[2,1\]

i: 18c\[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组合算法(m个n选1)，包括了方面的内容，希望对Java教程有兴趣的朋友有所帮助。

[21086a7026c92bfd7240ae238563fcc2.png]: /images/20221024/e1a5f3ffede04e26a0f462d26844b56b.png

java 算法 n_[转]Java组合算法（m个n选1）

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关计算组合数C(m, n)

相关无重复元素的组合算法/n个列表中取n个不同的数

相关字节2-1 算法n 进制转m进制2021-02

相关 java 算法 n_[转]Java组合算法（m个n选1）

相关每日一算法:m元素中取n个元素(高效算法)

相关生成{1,2,...,n}的排列的算法-组合数学

相关算法-1到n中所有和为m的组合

相关 m个数字任选n个数组进行组合

相关【排列组合】排列组合 "n个球放入m个盒子m"问题

相关 [LeetCode] java的排列与组合C(m,n)、A(m,n)