Java實(shí)現(xiàn)通用組合算法
作者：幫考網(wǎng)
Java是一種簡(jiǎn)單的，面向?qū)ο蟮模植际降模忉屝偷模寻踩模Y(jié)構(gòu)中立的，可移植的，性能優(yōu)異、多線程的動(dòng)態(tài)語(yǔ)言。通用組合算法是經(jīng)典數(shù)據(jù)結(jié)構(gòu)算法。本文介紹的是通用組合算法用Java來(lái)實(shí)現(xiàn)，一起來(lái)看。
Java實(shí)現(xiàn)通用組合算法，存在一個(gè)類似{31311133,33113330}這樣的集合，經(jīng)過8取5組合，其他位置用非字母數(shù)字字符替代，比如使用*號(hào)，得到類似{3***1133,***13330,... ...}這樣的集合;
現(xiàn)在有這樣的需求：
存在一個(gè)類似{31311133,33113330}這樣的集合，經(jīng)過8取5組合，其他位置用非字母數(shù)字字符替代，比如使用*號(hào)，得到類似{3***1133,***13330,... ...}這樣的集合;
還要求對(duì)于{3***1133,***13330}這樣的集合，再次經(jīng)過5取3組合，其他位置用非字母數(shù)字字符替代，比如使用*號(hào)，得到類似{*****133,*****330,3***1*3*,... ...}這樣的集合。
對(duì)于這樣的要求，實(shí)現(xiàn)的思路如下：
首先，主要思想是基于信息編碼原理，通過掃描字符串，將10組合變?yōu)?1組合。
其次，對(duì)于每個(gè)數(shù)字字符串，設(shè)置一個(gè)單線程，在單線程類中設(shè)置一個(gè)List用來(lái)存放待處理數(shù)字字符串(可能含有*號(hào)，或者不含有)中每個(gè)數(shù)字的(而非*號(hào))索引位置值;
再次，設(shè)置BitSet來(lái)標(biāo)志每個(gè)位置是否被*號(hào)替換得到新的組合字符串。
***，在掃描原始待處理數(shù)字字符串的過程中，根據(jù)設(shè)置的字符列表List中索引，來(lái)操作BitSet，對(duì)于每一個(gè)BitSet得到一個(gè)新的組合。
使用Java語(yǔ)言實(shí)現(xiàn)如下：
- 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;
- /**
- * 通用組合拆分類(基于單線程)
- * 可以完成兩種功能：
- * ***，可以將完全數(shù)字串拆分成為含有*號(hào)的字符串。
- * 例如：輸入集合{31311133,33113330}，Splitter類會(huì)遍歷該集合，對(duì)每個(gè)字符串，創(chuàng)建一個(gè)SplitterThread
- * 線程來(lái)處理，如果是2取1組合，即starCount=8-2=6，經(jīng)過線程處理得到類似******33,*****1*3等結(jié)果
- * 第二，根據(jù)從帶有*號(hào)的字符串經(jīng)過拆分過濾后得到的字符串集合，對(duì)其中每一個(gè)字符串進(jìn)行組合
- * 例如：輸入集合5取1組合字符串集合{3***1133,***113330}
- * CommonSplitter類會(huì)遍歷該集合，對(duì)每個(gè)帶有*號(hào)的字符串，創(chuàng)建一個(gè)SplitterThread
- * 線程來(lái)處理，如果是2串1組合，即starCount=8-3-2=3，經(jīng)過線程處理得到類似******33,*****1*3等結(jié)果
- * @author 時(shí)延軍
- */
- public class CommonSplitter {
- private int starCount;
- private boolean duplicate;
- private Collection filteredContainer;
- public Collection getFilteredContainer() {
- return filteredContainer;
- }
- /**
- * 構(gòu)造一個(gè)Spilitter實(shí)例
- * @param container 輸入的待處理字符串集合
- * @param starCount 如果對(duì)于長(zhǎng)度為N的數(shù)字字符串，進(jìn)行M組合(即N取M)，則starCount=N-M
- * @param duplicate 是否去重
- */
- public CommonSplitter(Collection container, int starCount, boolean duplicate) {
- this.duplicate = duplicate;
- this.starCount = starCount;
- if(this.duplicate) { // 根據(jù)指定是否去重的選擇，選擇創(chuàng)建容器
- filteredContainer = Collections.synchronizedSet(new HashSet());
- }
- else {
- filteredContainer = Collections.synchronizedList(new ArrayList());
- }
- Iterator it = container.iterator();
- while(it.hasNext()) {
- new Thread(new SplitterThread(it.next().trim())).start();
- }
- try {
- Thread.sleep(50);
- } catch (InterruptedException e) {
- e.printStackTrace();
- }
- }
- /**
- * 對(duì)一個(gè)指定的N場(chǎng)比賽的長(zhǎng)度為N的單式投注字符串進(jìn)行組合
- * 輸入單式投注注字符串string，例如31311133，組合得到類似******33,*****1*3,... ...結(jié)果的集合
- *
- * @author 時(shí)延軍
- */
- class SplitterThread implements Runnable {
- private char[] charArray;
- private int len; // 數(shù)字字符的個(gè)數(shù)
- List occupyIndexList = new ArrayList(); // 統(tǒng)計(jì)字符串中沒有帶*的位置的索引
- private List container = new ArrayList();
- private BitSet startBitSet; // 比特集合起始狀態(tài)
- private BitSet endBitSet; // 比特集合終止?fàn)顟B(tài)，用來(lái)控制循環(huán)
- public SplitterThread(String string) {
- this.charArray = string.toCharArray();
- this.len = string.replace("*", "").length();
- this.startBitSet = new BitSet(len);
- this.endBitSet = new BitSet(len);
- // 初始化startBitSet，左側(cè)占滿*符號(hào)
- int count = 0; //
- for (int i=0; i
- if(charArray[i] != '*') {
- if(count < starCount) {
- this.startBitSet.set(i, true);
- count++;
- }
- occupyIndexList.add(i);
- }
- }
- // 初始化endBit，右側(cè)占滿*符號(hào)
- count =0;
- for (int i = string.length()-1; i > 0; i--) {
- if(charArray[i] != '*') {
- if(count < starCount) {
- this.endBitSet.set(i, true);
- count++;
- }
- ccupyIndexList.add(i);
- }
- }
- // 根據(jù)起始startBitSet，構(gòu)造帶*的組合字符串并加入容器
- char[] charArrayClone = this.charArray.clone();
- for (int i=0; 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; // 統(tǒng)計(jì)遇到10后，左邊0的個(gè)數(shù)
- int oneCount = 0; // 統(tǒng)計(jì)遇到10后，左邊1的個(gè)數(shù)
- int pos = 0; // 記錄當(dāng)前遇到10的索引位置
- char[] charArrayClone = this.charArray.clone();
- // 遍歷startBitSet來(lái)確定10出現(xiàn)的位置
- for (int i=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變?yōu)?1
- this.startBitSet.set(this.occupyIndexList.get(i), false);
- this.startBitSet.set(this.occupyIndexList.get(i+1), true);
- break;
- }
- }
- // 將遇到10后，左側(cè)的1全部移動(dòng)到最左側(cè)
- 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
- 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
- if (this.startBitSet.get(this.occupyIndexList.get(i))) {
- charArrayClone[this.occupyIndexList.get(i)] = '*';
- }
- }
- this.container.add(new String(charArrayClone));
- }
- }}}
#p#
測(cè)試用例如下所示：
- 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 container, int starCount, boolean duplicate) {
- this.splitter = new CommonSplitter(container, starCount, duplicate);
- }
- public void testSplliter() {
- Collection container = new ArrayList();
- 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 container = new ArrayList();
- 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 container = new ArrayList();
- 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 場(chǎng):310
- String multiSeq = "310,310,310,310,310,310,310,310";
- Collection 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());
- }
- }
上述測(cè)試耗時(shí)大約2s左右。
上述算法實(shí)現(xiàn)主要是針對(duì)兩種條件進(jìn)行實(shí)現(xiàn)的，即：
***個(gè)是完全數(shù)字字符串 ——> 帶有*號(hào)的組合數(shù)字字符串;
第二個(gè)帶有*號(hào)的組合數(shù)字字符串 ——> 在該基礎(chǔ)上繼續(xù)組合得到帶有*號(hào)的組合數(shù)字字符串。
如果使用上述算法實(shí)現(xiàn)處理***個(gè)條件，由于使用了列表List來(lái)記錄索引，使執(zhí)行速度略微低一點(diǎn)，比之于前面實(shí)現(xiàn)的不使用List列表來(lái)處理。
【編輯推薦】
責(zé)任編輯：于鐵
來(lái)源：
幫考網(wǎng)
