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; } }
publicclass 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 */ publicvoid 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); } 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)!=leftCom.getStatus()){ leftCom.setStatus(this.conversionChar(leftMarker)); } } } } } /** * 转换 * @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; } }
页:
[1]