`
yaozhiqiang109
  • 浏览: 119718 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

JAVA组合算法的一个实现

    博客分类:
  • JAVA
阅读更多

描述:一个数组或集合对象,其下标表示1到m个数,数组元素的值为1表示其下标  

  代表的数被选中,为0则没选中。    

  首先初始化,将数组前n个元素置1,表示第一个组合为前n个数。    

  然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为  

  “01”组合,同时将其左边的所有“1”全部移动到数组的最左端。    

  当第一个“1”移动到数组的m-n的位置,即n个“1”全部移动到最右端时,就得  

  到了最后一个组合。 

 

例如求5中选3的组合:    

  1   1   1   0   0   //1,2,3    

  1   1   0   1   0   //1,2,4    

  1   0   1   1   0   //1,3,4    

  0   1   1   1   0   //2,3,4    

  1   1   0   0   1   //1,2,5    

  1   0   1   0   1   //1,3,5    

  0   1   1   0   1   //2,3,5    

  1   0   0   1   1   //1,4,5    

  0   1   0   1   1   //2,4,5    

  0   0   1   1   1   //3,4,5  

public class CombinationBean implements Serializable{

    private static final long serialVersionUID = 5420132066969835048L;
    /**
     * 值
     */
    private String combinationValue;
    /**
     * true表示选中 false表示为选中
     */
    private boolean status=false;
    
    public String getCombinationValue() {
        return combinationValue;
    }
    public void setCombinationValue(String combinationValue) {
        this.combinationValue = combinationValue;
    }
    public boolean getStatus() {
        return status;
    }
    public void setStatus(boolean status) {
        this.status = status;
    }
    
    
}
 

public  class CombinationArithmetic {

    private Set<List<CombinationBean>> result=new HashSet<List<CombinationBean>>();
    
    private List<CombinationBean> basicCombination=null;
    
    public CombinationArithmetic(List<String> combinationlist,int combinationNum){
        basicCombination=new ArrayList<CombinationBean>();
        this.getBasicCombination(combinationlist, combinationNum);
    }
    /**
     * 初始化基本的组合list
     * @param combinationlist
     * @param combinationNum
     * @create_time 2011-4-27 上午11:31:26
     */
    public  void getBasicCombination(List<String> combinationlist,int combinationNum){
        for (String element : combinationlist) {
            CombinationBean combination=new CombinationBean();
            combination.setCombinationValue(element);
            if(basicCombination.size()<combinationNum)
                combination.setStatus(true);
            basicCombination.add(combination);
        }
        result.add(basicCombination);
    }
    /**
     * 返回一个组合的是否选中的标识
     * @param basic
     * @return
     * @create_time 2011-4-27 下午03:47:46
     */
    public String getCombinationMarker(List<CombinationBean> basic){
        StringBuffer sBuffer=new StringBuffer();
        for (CombinationBean combinationBean : basic) {
            if(combinationBean.getStatus()){
                sBuffer.append(1);
            }else{
                sBuffer.append(0);
            }
        }
        return sBuffer.toString();
    }
    
    /**
     * 返回'10'标识前面所有需要左移的项
     * @param marker
     * @param status
     * @return
     * @create_time 2011-4-27 下午06:25:47
     */
    public char[] processChoiceMarker(String marker){
        int position=marker.indexOf("10");
        String left=marker.substring(0, position);
        int leftLocation=left.indexOf("0");
        int changeLocation=left.lastIndexOf("1");
        char[] allMarkerLeft=new char[]{};
        if(leftLocation>-1 && changeLocation>-1){
            char[] status=left.toCharArray();
            Arrays.sort(status);
            StringBuffer sBuffer=new StringBuffer();
            for(int i=status.length-1;i>-1;i--){
                sBuffer.append(status[i]);
            }
            allMarkerLeft=sBuffer.toString().toCharArray();
        }
        
        return allMarkerLeft;
    }
    /**
     * 递归获取所有的组合
     * @param combinationNum
     * @param basic
     * @create_time 2011-4-27 下午07:01:43
     */
    public void compose(int combinationNum,List<CombinationBean> basic){
        List<CombinationBean> copyCom=new ArrayList<CombinationBean>();
        for (CombinationBean element : basic) {
            CombinationBean copyElement=new CombinationBean();
            copyElement.setCombinationValue(element.getCombinationValue());
            copyElement.setStatus(element.getStatus());
            copyCom.add(copyElement);
        }
        this.moveLeftRecurion(copyCom);
        result.add(copyCom);
        if(!this.endRecursion(combinationNum))
            compose(combinationNum,copyCom);
    }
    /**
     * 将'10'(选中与没有选中的场次的组合)标识前面所有已选中的场次前移到最左边
     * @param copyCom
     * @create_time 2011-4-27 下午06:02:49
     */
    public void moveLeftRecurion(List<CombinationBean> copyCom){
        String marker=this.getCombinationMarker(copyCom);
        int position=marker.indexOf("10");
        if(position>-1 && position<copyCom.size()){
            CombinationBean com=copyCom.get(position);
            com.setStatus(false);
            CombinationBean comBean=copyCom.get(position+1);
            comBean.setStatus(true);
            char[] leftMarker=this.processChoiceMarker(marker);
            if(leftMarker!=null && leftMarker.length>0){
                for (int i=0;i<leftMarker.length;i++) {
                    CombinationBean leftCom=copyCom.get(i);
                    if(this.conversionChar(leftMarker[i])!=leftCom.getStatus()){
                        leftCom.setStatus(this.conversionChar(leftMarker[i]));
                    }
                }
            }
        }
    }
    /**
     * 转换
     * @param c
     * @return
     * @create_time 2011-4-27 下午06:37:25
     */
    public boolean conversionChar(char c){
        if(c=='1')
            return true;
        return false;
    }
    
    /**
     * 递归终结判断
     * @param combinationNum
     * @return
     * @create_time 2011-4-27 下午06:03:10
     */
    public boolean endRecursion(int combinationNum){
        boolean status=false;
        for (Iterator<List<CombinationBean>> iter = result.iterator(); iter.hasNext();) {   
            List<CombinationBean> endComList=iter.next();
            if(endComList==null || endComList.size()==0 || endComList.size()<combinationNum)
                return false;
            int count=0;
            for (int i=endComList.size()-1;i>=endComList.size()-combinationNum;i--) {
                CombinationBean com=endComList.get(i);
                if(com.getStatus()){
                    count=count+1;
                }
            }
            if(count==combinationNum)
                status=true;
        }
        return status;
    }
    /**
     * 判段这两场比赛是否是被选中和没有被选中即'10'组合
     * @param com
     * @param comBean
     * @return
     * @create_time 2011-4-27 下午07:04:21
     */
    public boolean judgeExchangeCondition(CombinationBean com,CombinationBean comBean){
        if(com.getStatus() && !comBean.getStatus())
            return true;
        return false;
    }
    /**
     * 得到所有的组合并拼接到一起
     * @return
     * @create_time 2011-4-27 下午07:04:55
     */
    public List<String> getComResult(int combinationNum){
        List<String> allComResult=new ArrayList<String>();
        List<String> comResult=new ArrayList<String>();
        for (Iterator<List<CombinationBean>> iter = result.iterator(); iter.hasNext();) {   
            List<CombinationBean> list=iter.next(); 
            if(list==null)
                continue;
            StringBuffer sBuffer=new StringBuffer();
            int count=0;
            for (CombinationBean combinationBean : list) {
                if(combinationBean.getStatus()){
                    sBuffer.append(combinationBean.getCombinationValue());
                    count=count+1;
                }
                if(combinationBean.getStatus() && count!=combinationNum)
                    sBuffer.append("|");
            }
            allComResult.add(sBuffer.toString());
        } 
        Set<String> set = new HashSet<String>();  
        for (String com : allComResult) {
            set.add(com);
        }
        for (Iterator<String> iter = set.iterator(); iter.hasNext();) {   
            set.add(iter.next());   
        }   
        comResult.clear();   
        comResult.addAll(set);  
        return comResult;
    }
    
    public List<CombinationBean> getBasicCombination() {
        return basicCombination;
    }
   
}
 
2
1
分享到:
评论

相关推荐

    Java排列组合算法分析和代码实现

    总之,这个资源包提供了一个很好的平台,让你能够深入理解并实践Java中的排列组合算法。通过学习和理解这些代码,你不仅可以增强算法设计能力,还能提高解决实际编程问题的能力。记得动手实践,结合文档和代码,将...

    1204 Java 遗传算法排课java sqlserver.rar_java排课算法_排课_排课系统java_遗传算法Java

    在教育领域,排课是一个典型的组合优化问题,需要考虑多方面的约束条件,如教师时间冲突、教室容量限制、课程时间安排等。遗传算法作为一种启发式搜索方法,能够通过模拟生物进化过程中的自然选择、遗传和突变等机制...

    java组合算法

    下面是一个递归版本的组合算法实现: ```java public class Test { public static void printCombinations(int[] nums, int start, ArrayList&lt;Integer&gt; combination) { // 打印当前组合 System.out.println...

    6位数,共有几种排列组合的算法java实现

    6位数,共有几种排列组合的算法,java实现

    多边形填充算法java实现

    在给定的标题“多边形填充算法java实现”中,我们可以推断这是一个Java编程项目,它实现了对多边形内部进行填充的功能。描述中提到的“扫描线算法”是实现这一功能的常见方法,这种方法基于逐行扫描图像并处理与...

    排列组合算法实现

    排列组合算法实现,支持模板类。支持重复数的排列。算法采用递归方法,简单易懂。

    java实现弗洛伊德算法

    以下是一个简化的Java代码示例: ```java public class FloydWarshall { public static void floydWarshall(int[][] graph, int n) { int[][] distance = new int[n][n]; // 初始化邻接矩阵 for (int i = 0; i ...

    java排列组合算法

    在Java中实现排列组合算法可以帮助我们解决很多实际问题,比如数据排序、数据筛选等。下面将详细介绍排列和组合的基本概念以及在Java中的实现方法。 **排列** 是指从n个不同元素中取出m(m≤n)个元素,按照一定的...

    Java排列组合_组合算法

    以下是一个基于描述中提及的list和set实现的组合算法的Java示例: ```java import java.util.*; public class Combination { public static void combination(List&lt;Integer&gt; list, int start, int end, List...

    实现了排列组合算法的类(JAVA).rar

    这个"实现了排列组合算法的类(JAVA).rar"文件提供了一种高效的JAVA实现,可以处理任意类型数组的排列和组合。下面将详细讨论排列组合的基本概念,以及在JAVA中实现这些算法的关键点。 排列是指从n个不同元素中...

    JAVA 经典算法(也有C实现)

    Java和C语言都是广泛应用于算法实现的编程语言,它们具有高效性和灵活性。"JAVA 经典算法(也有C实现)"这个资源包含了一些在软件开发中常用的、经典的算法,旨在帮助开发者提升算法思维和程序设计能力。 首先,让...

    Java排列组合算法

    本文将深入探讨Java中实现排列组合算法的方法,帮助开发者更好地理解和运用这些概念。 排列是有序的选择,而组合是无序的选择。在Java中,我们可以使用递归、回溯法或者迭代的方式来实现这两种算法。下面我们将详细...

    arima 算法 JAVA 实现.zip

    文件名“arima”可能是一个包含ARIMA算法实现的Java源代码文件,或者是一个包含测试数据和结果的文件。为了更好地理解和使用这个文件,你需要阅读代码并理解其实现细节。 总之,ARIMA模型是时间序列预测的重要工具...

    维吉尼亚加密算法的JAVA实现

    这种加密算法因其复杂性和在当时的安全性而受到赞誉,它通过使用多个凯撒密码(每个字母按固定位数偏移)的组合来构建一个可变的密钥表,使得加密过程更为复杂,难以破解。 在Java中实现维吉尼亚加密算法,我们需要...

    java组合的算法

    本篇文章将深入探讨Java中的组合算法,并通过一个名为"A1.java"的代码示例进行讲解。 组合模式的核心思想是"has-a"关系,即一个对象包含其他对象,这与继承的"is-a"关系不同。在Java中,我们通常通过接口或抽象类来...

    gray码生成组合算法的java代码

    本项目"gray码生成组合算法的java代码"是基于Java编程语言实现的,旨在结合组合数学原理生成Gray码。在实际编程中,生成Gray码通常涉及到循环移位和异或操作。下面将详细讲解这个程序可能涉及的知识点: 1. **Java...

    simhash-java Java实现simhash算法的简单实现.zip

    在Java环境下实现SimHash算法,可以帮助开发者在处理大量文本数据时快速识别重复或相似的信息。 SimHash算法的基本步骤如下: 1. **分词**:首先,我们需要将输入的文本进行分词,将连续的字符序列分割成单独的...

    基于java的遗传算法设计与实现

    遗传算法是一种模拟自然界...总之,Java为实现遗传算法提供了一个强大而灵活的平台,通过合理的设计和编程,可以构建出高效且易于维护的遗传算法求解器。在实际应用中,应结合具体问题调整算法参数,以达到最佳性能。

    Apriori算法的Java实现

    读取数据后,我们需要将其转化为可以供Apriori算法使用的格式,比如一个项集的集合,每个项集包含一系列的项(例如,商品ID)。 接着,我们需要实现Apriori的核心部分。算法分为两步:生成候选集和评估支持度。生成...

    各种算法的java实现

    在编程领域,Java是一种广泛应用的面向对象的编程语言,以其平台独立性和强大的功能深受开发者喜爱。...而对于有一定经验的开发者,这同样是一个很好的参考资料,可以用来复习和巩固算法知识,提升自己的编程技巧。

Global site tag (gtag.js) - Google Analytics