Java实现通用组合算法
发布时间：2010/9/9 10:28:01 来源：城市学习网 编辑：ziteng
现在有这样的需求：
存在一个类似{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语言实现如下：
package org.shirdrn;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
/**
* 通用组合拆分类(基于单线程)
*
* 可以完成两种功能：
*
* 第一，可以将完全数字串拆分成为含有*号的字符串。<br>
* 例如：输入集合{31311133,33113330}，Splitter类会遍历该集合，对每个字符串，创建一个SplitterThread<br>
* 线程来处理，如果是2取1组合，即starCount=8-2=6，经过线程处理得到类似******33,*****1*3等结果
*
* 第二，根据从带有*号的字符串经过拆分过滤后得到的字符串集合，对其中每一个字符串进行组合<br>
* 例如：输入集合5取1组合字符串集合{3***1133,***113330}<br>
*
* CommonSplitter类会遍历该集合，对每个带有*号的字符串，创建一个SplitterThread<br>
* 线程来处理，如果是2串1组合，即starCount=8-3-2=3，经过线程处理得到类似******33,*****1*3等结果
*
* @author 时延军
*
*/
public class CommonSplitter {
private int starCount;
private boolean duplicate;
private Collection<String> filteredContainer;
public Collection<String> getFilteredContainer() {
return filteredContainer;
}
/**
* 构造一个Spilitter实例
*
* @param container 输入的待处理字符串集合
* @param starCount 如果对于长度为N的数字字符串，进行M组合（即N取M），则starCount=N-M
* @param duplicate 是否去重
*/
public CommonSplitter(Collection<String> container, int starCount, boolean duplicate) {
this.duplicate = duplicate;
this.starCount = starCount;
if(this.duplicate) { // 根据指定是否去重的选择，选择创建容器
filteredContainer = Collections.synchronizedSet(new HashSet<String>());
}
else {
filteredContainer = Collections.synchronizedList(new ArrayList<String>());
}
Iterator<String> it = container.iterator();
while(it.hasNext()) {
new Thread(new SplitterThread(it.next().trim())).start();
}
try {
Thread.sleep(50);
} catch (InterruptedException e) {
e.printStackTrace();
}
} [NextPage] /**
* 对一个指定的N场比赛的长度为N的单式投注字符串进行组合<br>
* 输入单式投注注字符串string，例如31311133，组合得到类似******33,*****1*3,... ...结果的集合
*
* @author 时延军
*
*/
class SplitterThread implements Runnable {
private char[] charArray;
private int len; // 数字字符的个数
List<Integer> occupyIndexList = new ArrayList<Integer>(); // 统计字符串中没有带*的位置的索引
private List<String> container = new ArrayList<String>();
private BitSet startBitSet; // 比特集合起始状态
private BitSet endBitSet; // 比特集合终止状态，用来控制循环
public SplitterThread(String string) {
this.charArray = string.toCharArray();
this.len = string.replace("*", "").length();
this.startBitSet = new BitSet(len);
this.endBitSet = new BitSet(len);
// 初始化startBitSet，左侧占满*符号
int count = 0; //
for (int i=0; i<string.length(); i++) {
if(charArray[i] != '*') {
if(count < starCount) {
this.startBitSet.set(i, true);
count++;
}
occupyIndexList.add(i);
}
}
// 初始化endBit，右侧占满*符号
count =0;
for (int i = string.length()-1; i > 0; i--) {
if(charArray[i] != '*') {
if(count < starCount) {
this.endBitSet.set(i, true);
count++;
}
occupyIndexList.add(i);
}
}
// 根据起始startBitSet，构造带*的组合字符串并加入容器
char[] charArrayClone = this.charArray.clone();
for (int i=0; i<string.length(); i++) {
if (this.startBitSet.get(i)) {
charArrayClone[i] = '*';
}
}
this.container.add(new String(charArrayClone));
}
public void run() {
this.split();
synchronized(filteredContainer) {
filteredContainer.addAll(this.container);
}
}
public void split() {
while(!this.startBitSet.equals(this.endBitSet)) {
int zeroCount = 0; // 统计遇到10后，左边0的个数
int oneCount = 0; // 统计遇到10后，左边1的个数
int pos = 0; // 记录当前遇到10的索引位置
char[] charArrayClone = this.charArray.clone();
// 遍历startBitSet来确定10出现的位置
for (int i=0; i<this.occupyIndexList.size()-1; 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;
}
} [NextPage] // 将遇到10后，左侧的1全部移动到最左侧
int count = Math.min(zeroCount, oneCount);
int startIndex = this.occupyIndexList.get(0);
int endIndex = 0;
if(pos>1 && count>0) {
pos--;
endIndex = this.occupyIndexList.get(pos);
for (int i=0; i<count; 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 (int i=0; i<this.occupyIndexList.size(); i++) {
if (this.startBitSet.get(this.occupyIndexList.get(i))) {
charArrayClone[this.occupyIndexList.get(i)] = '*';
}
}
this.container.add(new String(charArrayClone));
}
}
}
}
测试用例如下所示：
package org.shirdrn;
import java.util.ArrayList;
import java.util.Collection;
import junit.framework.TestCase;
import org.shirdrn.util.GoodTools;
public class TestCommonSplitter extends TestCase {
private CommonSplitter splitter;
public void setSplitter(Collection<String> container, int starCount, boolean duplicate) {
this.splitter = new CommonSplitter(container, starCount, duplicate);
}
public void testSplliter() {
Collection<String> container = new ArrayList<String>();
container.add("1*10**");
int starCount = 2;
boolean duplicate = true;
this.setSplitter(container, starCount, duplicate);
System.out.println(this.splitter.getFilteredContainer());
}
public void testSplliter3() {
Collection<String> container = new ArrayList<String>();
container.add("1*10*1300*");
int starCount = 3;
boolean duplicate = true;
this.setSplitter(container, starCount, duplicate);
System.out.println(this.splitter.getFilteredContainer());
assertEquals(35, this.splitter.getFilteredContainer().size());
}
public void testNoStar() {
Collection<String> container = new ArrayList<String>();
container.add("3110330");
int starCount = 3;
boolean duplicate = true;
this.setSplitter(container, starCount, duplicate);
System.out.println(this.splitter.getFilteredContainer());
assertEquals(35, this.splitter.getFilteredContainer().size());
}
public void testSplitter_8_310() {
// 8 场:310
String multiSeq = "310,310,310,310,310,310,310,310";
Collection<String> container = GoodTools.getNSingleList(multiSeq);
assertEquals(6561, container.size());
int starCount = 4;
boolean duplicate = false;
this.setSplitter(container, starCount, duplicate);
assertEquals(459270, this.splitter.getFilteredContainer().size());
}
}
上述测试耗时大约2s左右。
上述算法实现主要是针对两种条件进行实现的，即：
第一个是完全数字字符串 ——> 带有*号的组合数字字符串；
第二个带有*号的组合数字字符串 ——> 在该基础上继续组合得到带有*号的组合数字字符串。
如果使用上述算法实现处理第一个条件，由于使用了列表List来记录索引，使执行速度略微低一点，比之于前面实现的不使用List列表来处理。
