Java中怎么實(shí)現(xiàn)一個(gè)通用組合算法

Java中怎么實(shí)現(xiàn)一個(gè)通用組合算法，針對這個(gè)問題，這篇文章詳細(xì)介紹了相對應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問題的小伙伴找到更簡單易行的方法。

Java實(shí)現(xiàn)通用組合算法，存在一個(gè)類似{31311133,33113330}這樣的集合，經(jīng)過8取5組合，其他位置用非字母數(shù)字字符替代，比如使用*號，得到類似{3***1133,***13330,... ...}這樣的集合;

現(xiàn)在有這樣的需求：

存在一個(gè)類似{31311133,33113330}這樣的集合，經(jīng)過8取5組合，其他位置用非字母數(shù)字字符替代，比如使用*號，得到類似{3***1133,***13330,... ...}這樣的集合;

還要求對于{3***1133,***13330}這樣的集合，再次經(jīng)過5取3組合，其他位置用非字母數(shù)字字符替代，比如使用*號，得到類似{*****133,*****330,3***1*3*,... ...}這樣的集合。

對于這樣的要求，實(shí)現(xiàn)的思路如下：

首先，主要思想是基于信息編碼原理，通過掃描字符串，將10組合變?yōu)?1組合。

其次，對于每個(gè)數(shù)字字符串，設(shè)置一個(gè)單線程，在單線程類中設(shè)置一個(gè)List用來存放待處理數(shù)字字符串(可能含有*號，或者不含有)中每個(gè)數(shù)字的(而非*號)索引位置值;

再次，設(shè)置BitSet來標(biāo)志每個(gè)位置是否被*號替換得到新的組合字符串。

***，在掃描原始待處理數(shù)字字符串的過程中，根據(jù)設(shè)置的字符列表List中索引，來操作BitSet，對于每一個(gè)BitSet得到一個(gè)新的組合。

使用Java語言實(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ù)字串拆分成為含有*號的字符串。  * 例如：輸入集合{31311133,33113330}，Splitter類會遍歷該集合，對每個(gè)字符串，創(chuàng)建一個(gè)SplitterThread  * 線程來處理，如果是2取1組合，即starCount=8-2=6，經(jīng)過線程處理得到類似******33,*****1*3等結(jié)果  * 第二，根據(jù)從帶有*號的字符串經(jīng)過拆分過濾后得到的字符串集合，對其中每一個(gè)字符串進(jìn)行組合  * 例如：輸入集合5取1組合字符串集合{3***1133,***113330}  * CommonSplitter類會遍歷該集合，對每個(gè)帶有*號的字符串，創(chuàng)建一個(gè)SplitterThread  * 線程來處理，如果是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 如果對于長度為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();  }  }  /**  * 對一個(gè)指定的N場比賽的長度為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)，用來控制循環(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è)占滿*符號  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è)占滿*符號  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來確定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));  }  }}}

測試用例如下所示：

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 場: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());  }  }

上述測試耗時(shí)大約2s左右。

上述算法實(shí)現(xiàn)主要是針對兩種條件進(jìn)行實(shí)現(xiàn)的，即：

***個(gè)是完全數(shù)字字符串 ——> 帶有*號的組合數(shù)字字符串;

第二個(gè)帶有*號的組合數(shù)字字符串 ——> 在該基礎(chǔ)上繼續(xù)組合得到帶有*號的組合數(shù)字字符串。

如果使用上述算法實(shí)現(xiàn)處理***個(gè)條件，由于使用了列表List來記錄索引，使執(zhí)行速度略微低一點(diǎn)，比之于前面實(shí)現(xiàn)的不使用List列表來處理。

關(guān)于Java中怎么實(shí)現(xiàn)一個(gè)通用組合算法問題的解答就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識。