Java编程实现通用组合算法.docx
《Java编程实现通用组合算法.docx》由会员分享，可在线阅读，更多相关《Java编程实现通用组合算法.docx（7页珍藏版）》请在冰点文库上搜索。
Java编程实现通用组合算法
Java编程实现通用组合算法
Java实现通用组合算法，存在一个类似{31311133，33113330}这样的集合，经过8取5组合，其他位置用非字母数字字符替代，比如使用*号，得到类似{3***1133，***13330，......}这样的集合;
现在有这样的需求：
存在一个类似{31311133，33113330}这样的集合，经过8取5组合，其他位置用非字母数字字符替代，比如使用*号，得到类似{3***1133，***13330，......}这样的集合;
还要求对于{3***1133，***13330}这样的集合，再次经过5取3组合，其他位置用非字母数字字符替代，比如使用*号，得到类似{*****133，*****330，3***1*3*，......}这样的集合。
对于这样的要求，实现的思路如下：
首先，主要思想是基于信息编码原理，通过扫描字符串，将10组合变为01组合。
其次，对于每个数字字符串，设置一个单线程，在单线程类中设置一个List用来存放待处理数字字符串（可能含有*号，或者不含有）中每个数字的（而非*号）索引位置值;
再次，设置BitSet来标志每个位置是否被*号替换得到新的组合字符串。
最后，在扫描原始待处理数字字符串的过程中，根据设置的字符列表List中索引，来操作BitSet，对于每一个BitSet得到一个新的组合。
使用Java语言实现如下：
packageorg.shirdrn;
importjava.util.ArrayList;
importjava.util.BitSet;
importjava.util.Collection;
importjava.util.Collections;
importjava.util.HashSet;
importjava.util.Iterator;
importjava.util.List;
/**
*通用组合拆分类（基于单线程）
*可以完成两种功能：
*第一，可以将完全数字串拆分成为含有*号的字符串。
*例如：
输入集合{31311133,33113330}，Splitter类会遍历该集合，对每个字符串，创建一个SplitterThread
*线程来处理，如果是2取1组合，即starCount=8-2=6，经过线程处理得到类似******33,*****1*3等结果
*第二，根据从带有*号的字符串经过拆分过滤后得到的字符串集合，对其中每一个字符串进行组合
*例如：
输入集合5取1组合字符串集合{3***1133,***113330}
*CommonSplitter类会遍历该集合，对每个带有*号的字符串，创建一个SplitterThread
*线程来处理，如果是2串1组合，即starCount=8-3-2=3，经过线程处理得到类似******33,*****1*3等结果
*@author时延军
*/
publicclassCommonSplitter{
privateintstarCount;
privatebooleanduplicate;
privateCollectionfilteredContainer;
publicCollectiongetFilteredContainer（）{
returnfilteredContainer;
}
/**
*构造一个Spilitter实例
*@paramcontainer输入的待处理字符串集合
*@paramstarCount如果对于长度为N的数字字符串，进行M组合（即N取M），则starCount=N-M
*@paramduplicate是否去重
*/
publicCommonSplitter（Collectioncontainer,intstarCount,booleanduplicate）{
this.duplicate=duplicate;
this.starCount=starCount;
if（this.duplicate）{//根据指定是否去重的选择，选择创建容器
filteredContainer=Collections.synchronizedSet（newHashSet（））;
}
else{
filteredContainer=Collections.synchronizedList（newArrayList（））;
}
Iteratorit=container.iterator（）;
while（it.hasNext（））{
newThread（newSplitterThread（it.next（）.trim（）））.start（）;
}
try{
Thread.sleep（50）;
}catch（InterruptedExceptione）{
e.printStackTrace（）;
}
}
/**
*对一个指定的N场比赛的长度为N的单式投注字符串进行组合
*输入单式投注注字符串string，例如31311133，组合得到类似******33,*****1*3,......结果的集合
*
*@author时延军
*/
classSplitterThreadimplementsRunnable{
privatechar[]charArray;
privateintlen;//数字字符的个数
ListoccupyIndexList=newArrayList（）;//统计字符串中没有带*的位置的索引
privateListcontainer=newArrayList（）;
privateBitSetstartBitSet;//比特集合起始状态
privateBitSetendBitSet;//比特集合终止状态，用来控制循环
publicSplitterThread（Stringstring）{
this.charArray=string.toCharArray（）;
this.len=string.replace（"*",""）.length（）;
this.startBitSet=newBitSet（len）;
this.endBitSet=newBitSet（len）;
//初始化startBitSet，左侧占满*符号
intcount=0;//
for（inti=0;i
if（charArray[i]!
='*'）{
if（count this.startBitSet.set（i,true）;
count++;
}
occupyIndexList.add（i）;
}
}
//初始化endBit，右侧占满*符号
count=0;
for（inti=string.length（）-1;i>0;i--）{
if（charArray[i]!
='*'）{
if（count this.endBitSet.set（i,true）;
count++;
}
ccupyIndexList.add（i）;
}
}
//根据起始startBitSet，构造带*的组合字符串并加入容器
char[]charArrayClone=this.charArray.clone（）;
for（inti=0;i
if（this.startBitSet.get（i））{
charArrayClone[i]='*';
}
}
this.container.add（newString（charArrayClone））;
}
publicvoidrun（）{
this.split（）;
synchronized（filteredContainer）{
filteredContainer.addAll（this.container）;
}}
publicvoidsplit（）{
while（!
this.startBitSet.equals（this.endBitSet））{
intzeroCount=0;//统计遇到10后，左边0的个数
intoneCount=0;//统计遇到10后，左边1的个数
intpos=0;//记录当前遇到10的索引位置
char[]charArrayClone=this.charArray.clone（）;
//遍历startBitSet来确定10出现的位置
for（inti=0;i
if（!
this.startBitSet.get（this.occupyIndexList.get（i）））{
zeroCount++;
}
if（this.startBitSet.get（this.occupyIndexList.get（i））
&&!
this.startBitSet.get（this.occupyIndexList.get（i+1）））{
pos=i;
oneCount=i-zeroCount;
//将10变为01
this.startBitSet.set（this.occupyIndexList.get（i）,false）;
this.startBitSet.set（this.occupyIndexList.get（i+1）,true）;
break;
}
}
//将遇到10后，左侧的1全部移动到最左侧
intcount=Math.min（zeroCount,oneCount）;
intstartIndex=this.occupyIndexList.get（0）;
intendIndex=0;
if（pos>1&&count>0）{
pos--;
endIndex=this.occupyIndexList.get（pos）;
for（inti=0;i
this.startBitSet.set（startIndex,true）;
this.startBitSet.set（endIndex,false）;
startIndex=this.occupyIndexList.get（i+1）;
pos--;
if（pos>0）{
endIndex=this.occupyIndexList.get（pos）;
}
}}
//将遇到1的位置用*替换
for（inti=0;i
if（this.startBitSet.get（this.occupyIndexList.get（i）））{
charArrayClone[this.occupyIndexList.get（i）]='*';
}
}
this.container.add（newString（charArrayClone））;
}
}}}
测试用例如下所示：
packageorg.shirdrn;
importjava.util.ArrayList;
importjava.util.Collection;
importjunit.framework.TestCase;
importorg.shirdrn.util.GoodTools;
publicclassTestCommonSplitterextendsTestCase{
privateCommonSplittersplitter;
publicvoidsetSplitter（Collectioncontainer,intstarCount,booleanduplicate）{
this.splitter=newCommonSplitter（container,starCount,duplicate）;
}
publicvoidtestSplliter（）{
Collectioncontainer=newArrayList（）;
container.add（"1*10**"）;
intstarCount=2;
booleanduplicate=true;
this.setSplitter（container,starCount,duplicate）;
System.out.println（this.splitter.getFilteredContainer（））;
}
publicvoidtestSplliter3（）{
Collectioncontainer=newArrayList（）;
container.add（"1*10*1300*"）;
intstarCount=3;
booleanduplicate=true;
this.setSplitter（container,starCount,duplicate）;
System.out.println（this.splitter.getFilteredContainer（））;
assertEquals（35,this.splitter.getFilteredContainer（）.size（））;
}
publicvoidtestNoStar（）{
Collectioncontainer=newArrayList（）;
container.add（"3110330"）;
intstarCount=3;
booleanduplicate=true;
this.setSplitter（container,starCount,duplicate）;
System.out.println（this.splitter.getFilteredContainer（））;
assertEquals（35,this.splitter.getFilteredContainer（）.size（））;
}
publicvoidtestSplitter_8_310（）{
//8场:
310
StringmultiSeq="310,310,310,310,310,310,310,310";
Collectioncontainer=GoodTools.getNSingleList（multiSeq）;
assertEquals（6561,container.size（））;
intstarCount=4;
booleanduplicate=false;
this.setSplitter（container,starCount,duplicate）;
assertEquals（459270,this.splitter.getFilteredContainer（）.size（））;
}
}
上述测试耗时大约2s左右。
上述算法实现主要是针对两种条件进行实现的，即：
第一个是完全数字字符串——>带有*号的组合数字字符串;
第二个带有*号的组合数字字符串——>在该基础上继续组合得到带有*号的组合数字字符串。
如果使用上述算法实现处理第一个条件，由于使用了列表List来记录索引，使执行速度略微低一点，比之于前面实现的不使用List列表来处理。
升级会员 