Java實現通用組合算法

　　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列表來處理

From:http://tw.wingwit.com/Article/program/Java/hx/201311/25538.html