package test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;
/**
* 计算满足特定要求的所有组合结果
* 算法应用场景:
* 有如下输入{1,2,3,4,5,6,2,3,4,5,6,2,3,4,5,6,2,3,4,5,6}，要求所有满足"和"在5和10之间的所有不重复组合
* @author xiadehu
* @version 1.0 2009-07-17
*/
public class CombinationCalculator {
/*
* 待计算数据
*/
private int[] iniArr=null;
/*
* 组合最大值
*/
private int max=0;
/*
* 组合最小值
*/
private int min=0;
/*
* 组合大小，组合结果个数的映射关系，用于优化算法
*/
private Map<Integer,Integer> resultMap = new HashMap<Integer,Integer>();
/*
* 计算后的结果
*/
List<CalculateCell> result = new ArrayList<CalculateCell>();
public CombinationCalculator(int[] initData,int sumMax,int sumMin){
this.iniArr=initData;
this.max=sumMax;
this.min=sumMin;
}
//开始计算
public void startCalculate(){
iniArr = init(iniArr);
loopCalculator(new int[]{iniArr[0]},new int[]{0},0);
}
//计算当前组合是否满足要求
public void calculate(CalculateCell cell){
int sum=sum(cell.getCurrCom());
Integer count= resultMap.get(cell.getCurrCom().length);
count = count==null?0:count;
//该组合匹配要求
if(isValid(sum)){
if(!result.contains(cell)){
result.add(cell);
}
resultMap.put(cell.getCurrCom().length, count+1);//用于优化算法，减少迭代次数，以后再做
}
}
//计算单元
class CalculateCell{
//组合数据
int[] currCom=null;
//数据在全部组合数组中的下标
int[] offIdx=null;
//循环的第几层
int currLoopIdx=0;
public CalculateCell(int[] currCom,int[] offIdx,int currLoopIdx){
this.currCom=currCom;
this.currLoopIdx=currLoopIdx;
this.offIdx=offIdx;
}
public int[] getCurrCom() {
return currCom;
}
public void setCurrCom(int[] currCom) {
this.currCom = currCom;
}
public int getCurrLoopIdx() {
return currLoopIdx;
}
public void setCurrLoopIdx(int currLoopIdx) {
this.currLoopIdx = currLoopIdx;
}
public int[] getOffIdx() {
return offIdx;
}
public void setOffIdx(int[] offIdx) {
this.offIdx = offIdx;
}
/**
*
* 覆盖equals方法，用于过滤重复结果
*
*/
public boolean equals(Object obj){
if(obj==null){
return false;
}
if(!(obj instanceof CalculateCell)){
return false;
}
CalculateCell objNew=(CalculateCell)obj;
if(this==obj){
return true;
}
if(objNew.getCurrCom()==null || this.currCom==null){
return false;
}
if(objNew.getCurrCom().length!=this.currCom.length){
return false;
}
for(int i=0;i<this.currCom.length;i++){
if(this.currCom[i]!=objNew.getCurrCom()[i]){
return false;
}
}
return true;
}
}
//克隆数组
private int[] clone(int[] in){
int[] out = new int[in.length];
for(int i=0;i<in.length;i++){
out[i]=in[i];
}
return out;
}
/**
* 核心算法，利用栈转换多层循环实现了基本的要求，算法优化空间较大
* @param currCom 当前组合数组
* @param offIdx 当前组合数组在原数组中的下标
* @param currLoopIdx 当前待循环的元素在currCom中的下标
*
*/
public void loopCalculator(int[] currComIn,int[] offIdxIn,int currLoopIdxIn){
//定义栈
Stack<CalculateCell> stack = new Stack<CalculateCell>();
//添加第一个元素到栈
stack.push(new CalculateCell(currComIn,offIdxIn,currLoopIdxIn));
while(!stack.isEmpty()){
CalculateCell cell = stack.pop();
int[] currCom=clone(cell.getCurrCom());//克隆一个数组，
int[] offIdx=clone(cell.getOffIdx());//克隆一个数组，
int currLoopIdx=cell.getCurrLoopIdx();
//计算，并将结果添加到集合内，便于计算完成后输出
calculate(cell);
//该层循环已到终点
if(isArriveEnd(offIdx,currLoopIdx)){
//是否有上层循环
if(!hasUpLoop(offIdx,currLoopIdx)){
//循环层数是否达到最大
if(isMaxLevelLoop(offIdx,currLoopIdx)){
continue;
}
//循环层数未达到最大
currCom=new int[currCom.length+1];
offIdx=new int[currCom.length];
for(int i=0;i<currCom.length;i++){
currCom[i]=iniArr[i];
offIdx[i]=i;
}
currLoopIdx=currCom.length-1;
stack.push(new CalculateCell(currCom,offIdx,currLoopIdx));
continue;
}
//有上层循环
currLoopIdx--;
stack.push(new CalculateCell(currCom,offIdx,currLoopIdx));
continue;
}
//循环未到终点,为最内层循环
if(isInnerLoop(offIdx,currLoopIdx)){
offIdx[currLoopIdx]++;
currCom[currLoopIdx]=iniArr[offIdx[currLoopIdx]];
stack.push(new CalculateCell(currCom,offIdx,currLoopIdx));
continue;
}
//循环未到终点,非最内层循环
offIdx[currLoopIdx]++;
currCom[currLoopIdx]=iniArr[offIdx[currLoopIdx]];
for(int i=currLoopIdx+1;i<currCom.length;i++){
offIdx[i] = offIdx[i-1]+1;
currCom[i]=iniArr[offIdx[i]];
}
currLoopIdx=currCom.length-1;
stack.push(new CalculateCell(currCom,offIdx,currLoopIdx));
}
}
/**
*
* 判断是否到达终点
*
*/
private boolean isArriveEnd(int[] offIdx,int currLoopIdx){
return offIdx[currLoopIdx]+(offIdx.length-currLoopIdx)==iniArr.length?true:false;
}
/**
*
* 判断是否有上一层循环
*
*/
private boolean hasUpLoop(int[] offIdx,int currLoopIdx){
return currLoopIdx==0?false:true;
}
/**
*
* 是否为最内层循环
*
*/
private boolean isInnerLoop(int[] offIdx,int currLoopIdx){
return currLoopIdx+1==offIdx.length?true:false;
}
/**
*
* 循环层数是否达到最大
*
*/
private boolean isMaxLevelLoop(int[] offIdx,int currLoopIdx){
return offIdx.length==iniArr.length?true:false;
}
/**
*
* 处理初始化数据，包括过滤重复和排序
*
*/
private int[] init(int[] a){
List<Integer> lst = new ArrayList<Integer>();
for(int i:a){
if(lst.contains(i)){
continue;
}
lst.add(i);
}
int[] result = new int[lst.size()];
for(int i=0;i<result.length;i++){
result[i]=lst.get(i);
}
Arrays.sort(result);
return result;
}
/**
*
* 统计和
*
*/
private int sum(int[] data){
int sum = 0;
for(int item:data){
sum += item;
}
return sum;
}
/**
*
* 判定是否满足组合的要求
*
*/
private boolean isValid(int sum){
return sum<=max && sum >= min ? true:false;
}
public Map<Integer, Integer> getResultMap() {
return resultMap;
}
public void setResultMap(Map<Integer, Integer> resultMap) {
this.resultMap = resultMap;
}
public List<CalculateCell> getResult() {
return result;
}
public void setResult(List<CalculateCell> result) {
this.result = result;
}
public static void main(String[] args){
int[] initdata = new int[]{1,2,3,4,5,6,2,3,4,5,6,2,3,4,5,6,2,3,4,5,6};
int sumMax = 10;
int sumMin = 5;
CombinationCalculator cal = new CombinationCalculator(initdata,sumMax,sumMin);
cal.startCalculate();
List<CalculateCell> result = cal.getResult();
for(CalculateCell cell:result){
int[] com = cell.getCurrCom();
int sum = 0;
String outStr="";
for(int i:com){
outStr = outStr + i+"+";
sum += i;
}
outStr = outStr.substring(0,outStr.length()-1);
outStr = outStr.concat("=").concat(String.valueOf(sum));
System.out.println(outStr);
}
}
}
|
