Java实现通用组合算法存在一个类似{}这样的集合经过取组合其他位置用非字母数字字符替代比如使用*号得到类似{****** }这样的集合
现在有这样的需求
存在一个类似{}这样的集合经过取组合其他位置用非字母数字字符替代比如使用*号得到类似{****** }这样的集合
还要求对于{******}这样的集合再次经过取组合其他位置用非字母数字字符替代比如使用*号得到类似{*************** }这样的集合
对于这样的要求实现的思路如下
首先主要思想是基于信息编码原理通过扫描字符串将组合变为组合
其次对于每个数字字符串设置一个单线程在单线程类中设置一个List用来存放待处理数字字符串（可能含有*号或者不含有）中每个数字的（而非*号）索引位置值
再次设置BitSet来标志每个位置是否被*号替换得到新的组合字符串
最后在扫描原始待处理数字字符串的过程中根据设置的字符列表List中索引来操作BitSet对于每一个BitSet得到一个新的组合
使用Java语言实现如下
package orgshirdrn;
import javautilArrayList;
import javautilBitSet;
import javautilCollection;
import javautilCollections;
import javautilHashSet;
import javautilIterator;
import javautilList;
/**
* 通用组合拆分类(基于单线程)
* 可以完成两种功能
* 第一可以将完全数字串拆分成为含有*号的字符串
* 例如输入集合{}Splitter类会遍历该集合对每个字符串创建一个SplitterThread
* 线程来处理如果是取组合即starCount==经过线程处理得到类似************等结果
* 第二根据从带有*号的字符串经过拆分过滤后得到的字符串集合对其中每一个字符串进行组合
* 例如输入集合取组合字符串集合{******}
* CommonSplitter类会遍历该集合对每个带有*号的字符串创建一个SplitterThread
* 线程来处理如果是串组合即starCount==经过线程处理得到类似************等结果
* @author 时延军
*/
public class CommonSplitter {
private int starCount;
private boolean duplicate;
private Collection filteredContainer;
public Collection getFilteredContainer() {
return filteredContainer;
}
/**
* 构造一个Spilitter实例
* @param container 输入的待处理字符串集合
* @param starCount 如果对于长度为N的数字字符串进行M组合(即N取M)则starCount=NM
* @param duplicate 是否去重
*/
public CommonSplitter(Collection container int starCount boolean duplicate) {
thisduplicate = duplicate;
thisstarCount = starCount;
if(thisduplicate) { // 根据指定是否去重的选择选择创建容器
filteredContainer = CollectionssynchronizedSet(new HashSet());
}
else {
filteredContainer = CollectionssynchronizedList(new ArrayList());
}
Iterator it = erator();
while(ithasNext()) {
new Thread(new SplitterThread(itnext()trim()))start();
}
try {
Threadsleep();
} catch (InterruptedException e) {
eprintStackTrace();
}
}
/**
* 对一个指定的N场比赛的长度为N的单式投注字符串进行组合
* 输入单式投注注字符串string例如组合得到类似************ 结果的集合
*
* @author 时延军
*/
class SplitterThread implements Runnable {
private char[] charArray;
private int len; // 数字字符的个数
List occupyIndexList = new ArrayList(); // 统计字符串中没有带*的位置的索引
private List container = new ArrayList();
private BitSet startBitSet; // 比特集合起始状态
private BitSet endBitSet; // 比特集合终止状态用来控制循环
public SplitterThread(String string) {
thischarArray = stringtoCharArray();
thislen = stringreplace(* )length();
thisstartBitSet = new BitSet(len);
thisendBitSet = new BitSet(len);
// 初始化startBitSet左侧占满*符号
int count = ; //
for (int i=; i
if(charArray[i] != *) {
if(count < starCount) {
thisstartBitSetset(i true);
count++;
}
occupyIndexListadd(i);
}
}
// 初始化endBit右侧占满*符号
count =;
for (int i = stringlength(); i > ; i) {
if(charArray[i] != *) {
if(count < starCount) {
thisendBitSetset(i true);
count++;
}
ccupyIndexListadd(i);
}
}
// 根据起始startBitSet构造带*的组合字符串并加入容器
char[] charArrayClone = thischarArrayclone();
for (int i=; i
if (thisstartBitSetget(i)) {
charArrayClone[i] = *;
}
}
ntaineradd(new String(charArrayClone));
}
public void run() {
thissplit();
synchronized(filteredContainer) {
filteredContaineraddAll(ntainer);
}}
public void split() {
while(!thisstartBitSetequals(thisendBitSet)) {
int zeroCount = ; // 统计遇到后左边的个数
int oneCount = ; // 统计遇到后左边的个数
int pos = ; // 记录当前遇到的索引位置
char[] charArrayClone = thischarArrayclone();
// 遍历startBitSet来确定出现的位置
for (int i=; i
if (!thisstartBitSetget(thisoccupyIndexListget(i))) {
zeroCount++;
}
if (thisstartBitSetget(thisoccupyIndexListget(i))
&& !thisstartBitSetget(thisoccupyIndexListget(i+))) {
pos = i;
oneCount = i zeroCount;
// 将变为
thisstartBitSetset(thisoccupyIndexListget(i) false);
thisstartBitSetset(thisoccupyIndexListget(i+) true);
break;
}
}
// 将遇到后左侧的全部移动到最左侧
int count = Mathmin(zeroCount oneCount);
int startIndex = thisoccupyIndexListget();
int endIndex = ;
if(pos> && count>) {
pos;
endIndex = thisoccupyIndexListget(pos);
for (int i=; i
thisstartBitSetset(startIndex true);
thisstartBitSetset(endIndex false);
startIndex = thisoccupyIndexListget(i+);
pos;
if(pos>) {
endIndex = thisoccupyIndexListget(pos);
}
}}
// 将遇到的位置用*替换
for (int i=; i
if (thisstartBitSetget(thisoccupyIndexListget(i))) {
charArrayClone[thisoccupyIndexListget(i)] = *;
}
}
ntaineradd(new String(charArrayClone));
}
}}}
测试用例如下所示
package orgshirdrn;
import javautilArrayList;
import javautilCollection;
import junitframeworkTestCase;
import orgshirdrnutilGoodTools;
public class TestCommonSplitter extends TestCase {
private CommonSplitter splitter;
public void setSplitter(Collection container int starCount boolean duplicate) {
thissplitter = new CommonSplitter(container starCount duplicate);
}
public void testSplliter() {
Collection container = new ArrayList();
containeradd(***);
int starCount = ;
boolean duplicate = true;
thissetSplitter(container starCount duplicate);
Systemoutprintln(thissplittergetFilteredContainer());
}
public void testSplliter() {
Collection container = new ArrayList();
containeradd(***);
int starCount = ;
boolean duplicate = true;
thissetSplitter(container starCount duplicate);
Systemoutprintln(thissplittergetFilteredContainer());
assertEquals( thissplittergetFilteredContainer()size());
}
public void testNoStar() {
Collection container = new ArrayList();
containeradd();
int starCount = ;
boolean duplicate = true;
thissetSplitter(container starCount duplicate);
Systemoutprintln(thissplittergetFilteredContainer());
assertEquals( thissplittergetFilteredContainer()size());
}
public void testSplitter__() {
// 场:
String multiSeq = ;
Collection container = GoodToolsgetNSingleList(multiSeq);
assertEquals( containersize());
int starCount = ;
boolean duplicate = false;
thissetSplitter(container starCount duplicate);
assertEquals( thissplittergetFilteredContainer()size());
}
}
上述测试耗时大约s左右
上述算法实现主要是针对两种条件进行实现的即
第一个是完全数字字符串 ——> 带有*号的组合数字字符串
第二个带有*号的组合数字字符串 ——> 在该基础上继续组合得到带有*号的组合数字字符串
如果使用上述算法实现处理第一个条件由于使用了列表List来记录索引使执行速度略微低一点比之于前面实现的不使用List列表来处理
