import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
//计算组合的算法
public class CombinationClass {
public CombinationClass()
{
}
//对于任意n选m个元素,如果m==0,则此次排法结束,如果m不为0,那么在n个元素中选择m个元素就是要首先在n个元素中选出一个元素,然后
//在其他n-1个元素中选择m-1个元素。因此,对于每一个n来讲,它的任务就是,将当前传入的集合中填充上自己的信息,然后比较是否有其他
//集合与自己所在集合相等如果这个集合长度为0,则重新建立一个集合,然后再把集合传入到其他的数据中。
public ArrayList<HashSet> computeCombine(int cardinalNum, int ordinalNum,int[] numList, HashSet resultSet,ArrayList<HashSet> resultList)
{
//拷贝副本,而不能引用原来的HashSet
HashSet resultSetEnter = (HashSet)resultSet.clone();
//如果m==0则此次排法结束
if(ordinalNum == 0)
{ //完毕一种排法,把它添加到序列中
resultList.add(resultSetEnter);
return resultList;
}
if(numList.length != cardinalNum)
return null;
int newList[] = new int[numList.length - 1];
for(int i = 0; i < numList.length; i ++)
{
//每次随便在cardinalNum中取出一个数,打印出来,然后在在其余的cardinalNum-1个数中取ordinal-1次
//如果集合长度为0,则新建一个集合
HashSet resultSetCopy =(HashSet)resultSet.clone();
if(resultSetCopy.size() == 0)
resultSetCopy = new HashSet();
resultSetCopy.add(numList[i]);
//如果有其他集合与本集合相等,则返回
boolean result = false;
for(int k = 0; k < resultList.size(); k ++)
{
HashSet hashSet = resultList.get(k);
result = HashSetEqual(hashSet,resultSetCopy);
//如果有集合和该集合相等,则跳出循环
if(result == true)
break;
}
//如果有集合和该集合相等,则进行下一次循环
if(result == true)
continue;
//在该集合中添加入该元素
//删掉numList[i]
for(int j = 0;j<i;j++)
{
newList[j] = numList[j];
}
for(int j = i + 1; j <= numList.length - 1; j ++)
{
newList[j - 1] = numList[j];
}
computeCombine(cardinalNum - 1,ordinalNum - 1, newList,resultSetCopy, resultList);
}
return null;
}
public static boolean HashSetEqual(HashSet hashSet, HashSet resultSetCopy)
{ int equal = 1;
Iterator it = hashSet.iterator();
if(resultSetCopy.size() == hashSet.size()){
while(it.hasNext())
{
if(equal == 0)
break;
if(equal == 1){
equal = 0;
int num = ((Integer)it.next()).intValue();
Iterator it2 = resultSetCopy.iterator();
while(it2.hasNext())
{
int num2 = ((Integer)it2.next()).intValue();
if(num == num2){
equal = 1;
break;
}
}
}
}
if(equal == 1)
return true;
else
return false;
}
return false;
}
}
//主方法
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
public class Main {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
CombinationClass combinationClass = new CombinationClass();
ArrayList<HashSet> resultList = new ArrayList<HashSet>();
combinationClass.computeCombine(8, 3, new int[]{1,2,3,4,5,6,7,8},new HashSet(), resultList);
System.out.println("BBBBBB" + resultList.size());
for(int i = 0; i < resultList.size(); i ++)
{
HashSet set = resultList.get(i);
Iterator it = set.iterator();
while(it.hasNext())
{
System.out.print(it.next() + " - ");
}
System.out.println();
}
}
}
分享到:
相关推荐
6位数,共有几种排列组合的算法,java实现
本资源附带文档解释了排列组合算法的实现和原理。其中排列算法是基于递归实现的,组合算法是基于高效的位移法实现的。代码是使用Java版实现的。
排列组合算法实现,支持模板类。支持重复数的排列。算法采用递归方法,简单易懂。
Java排列组合_组合算法,利用list及set的无序性, 通过递归实现,不同于以往的排列组合 自娱自乐
一个已经关闭的googlecode项目,基于正交法对Pairwise Testing算法进行的java实现,具体说明见内部文档
所使用的算法应该是效率最高的算法,而且这两个类都只是对需要排列组合的数组的下标进行处理,所以能对任何类型的数组进行排列组合。
此外,文档还提供了各种排列组合算法的详细代码示例和实现细节,包括递归和迭代方法。文档还涵盖了高级主题,如如何计算有重复元素的排列组合数量,以及如何优化这些算法的性能。 无论您是Java编程的初学者还是有...
介绍了几种用JAVA实现的排列组合算法,有需要的朋友可以参考一下
组合算法JSP程序,以java算法为基础,描述组合算法的运行机制和实现
基于java的国密SM系列加解密算法,包含SM1、SM2、SM3、SM4的加解密java实现
不同的天气因素组合会产生两种后果,也就是分成2类:能进行活动或不能。我们用P表示该活动可以进行,N表示该活动无法进行。 下表描述样本集合是不同天气因素对该活动的影响。 Attribute class outlook ...
System.out.println("对整数数组进行组合:C(n,n)"); int[] intArray=new int[4]; for(int i=0;i;i++){ intArray[i]=i+1; } System.out.println("对整数数组进行组合:C(4,4)"); Combination ...
全排列的非递归实现。输入1,2,3 得到 [1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]六种组合
文档中涵盖了有序数组合并的基本概念,包括如何将两个有序数组合并为一个,以及如何在Java中实现合并有序数组。此外,文档还包括一个逐步指南,介绍了如何在Java中实现合并有序数组,包括详细的代码示例和实现细节。...
主要介绍了Java实现字符数组全排列的方法,涉及Java针对字符数组的遍历及排序算法的实现技巧,需要的朋友可以参考下
用Java实现的词频统计,代码。为了统计词汇出现频率,最简单直接的做法是另外建一个Map:key是单词,value是次数。将文章从头读到尾,读到一个单词就到Map里查一下,如果查到了则次数加一,没查到则往Map里一扔。...
CART算法的全称是分类回归树算法,他是一个二元分类,采用的是类似于熵的基尼指数作为分类决策,形成决策树后之后还要进行剪枝,我自己在实现整个算法的时候采用的是代价复杂度算法,详细介绍链接 KNN K最近邻算法...
在Java实现中,归并排序通过递归调用mergeSortHelper方法将数组划分为更小的子数组,并在最后使用merge方法将有序子数组合并成一个完整的数组。归并排序虽然需要额外的空间来存储临时数组,但其稳定的性能和可并行化...
网上找了些java实现24点小游戏的算法,看了一下,头都晕了! 自己写了一个类,各位可以看一下思路,如果需要的话,只要实例化PointGame类并在构造方法里传递参与计算的四个数字和需要的结果就好了,然后调用get...
实现了排列组合算法的类(JAVA),实现了排列组合算法的类(JAVA)