我这里只写了组合的算法。 假设现有 M=4 个数据 a,b,c,d。从中随机抽取n个数,n为1—4个数据进行组合。那么数学中的计算组合方式为C(4,1) + C(4,2) + C(4,3) + C(4,4) = 4 + 6
我这里只写了组合的算法。
假设现有 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 resList = new ArrayList<>(); //初始化需要组合的数据 String[] arr = new String[]{"a","b","c","d"}; List initList = new LinkedList(Arrays.asList(arr)); //map中 key:组合数据的前缀,value:未参与组合的数据 Map> 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 syList = initList.subList(i+1,initList.size()); map.put(pj,syList); } } combinLoop(map,resList); System.out.println(resList.size()); } public static void combinLoop(Map> map,List resList){ for (Map.Entry> entry : map.entrySet()) { String prefix = entry.geTKEy(); List list = entry.getValue(); Map> 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 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与下一次参与循环的数据组合,依次进行直到所有数据循环完成。
代码如下:
public static void combine2(){ String[] arr = new String[]{"a","b","c","d"}; //初始化数据 List initList = Arrays.asList(arr); //结果集 List resultList = new ArrayList<>(); for (String init : initList) { //重新赋值上次循环组合后得到的resultList结果集 List list = new ArrayList<>(resultList); //resultList添加初始数据 resultList.add(init); for (String pr : list) { //把前一次得到的resultList 与当前数据重新进行组合 resultList.add(pr + init); } } }
来源地址:https://blog.csdn.net/yusewuhen/article/details/130603555
--结束END--
本文标题: java实现排列组合算法
本文链接: https://www.lsjlt.com/news/387952.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-04-01
2024-04-03
2024-04-03
2024-01-21
2024-01-21
2024-01-21
2024-01-21
2023-12-23
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
一口价域名售卖能注册吗?域名是网站的标识,简短且易于记忆,为在线用户提供了访问我们网站的简单路径。一口价是在域名交易中一种常见的模式,而这种通常是针对已经被注册的域名转售给其他人的一种方式。
一口价域名买卖的过程通常包括以下几个步骤:
1.寻找:买家需要在域名售卖平台上找到心仪的一口价域名。平台通常会为每个可售的域名提供详细的描述,包括价格、年龄、流
443px" 443px) https://www.west.cn/docs/wp-content/uploads/2024/04/SEO图片294.jpg https://www.west.cn/docs/wp-content/uploads/2024/04/SEO图片294-768x413.jpg 域名售卖 域名一口价售卖 游戏音频 赋值/切片 框架优势 评估指南 项目规模 安全指南 Osprey 游戏分析 游戏调试 游戏图形 游戏物理 开源库 魔方破解 游戏安全
0