Java中怎么实现一个通用组合算法

Java中怎么实现一个通用组合算法，针对这个问题，这篇文章详细介绍了相对应的分析和解答，希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

Java实现通用组合算法，存在一个类似{31311133,33113330}这样的集合，经过8取5组合，其他位置用非字母数字字符替代，比如使用*号，得到类似{3***1133,***13330,... ...}这样的集合;

现在有这样的需求：

存在一个类似{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;   /**  * 通用组合拆分类(基于单线程)  * 可以完成两种功能：  * ***，可以将完全数字串拆分成为含有*号的字符串。  * 例如：输入集合{31311133,33113330}，Splitter类会遍历该集合，对每个字符串，创建一个SplitterThread  * 线程来处理，如果是2取1组合，即starCount=8-2=6，经过线程处理得到类似******33,*****1*3等结果  * 第二，根据从带有*号的字符串经过拆分过滤后得到的字符串集合，对其中每一个字符串进行组合  * 例如：输入集合5取1组合字符串集合{3***1133,***113330}  * CommonSplitter类会遍历该集合，对每个带有*号的字符串，创建一个SplitterThread  * 线程来处理，如果是2串1组合，即starCount=8-3-2=3，经过线程处理得到类似******33,*****1*3等结果  * @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=N-M  * @param duplicate 是否去重  */ public CommonSplitter(Collection container, int starCount, boolean duplicate) {  this.duplicate = duplicate;  this.starCount = starCount;  if(this.duplicate) { // 根据指定是否去重的选择，选择创建容器  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();  }  }  /**  * 对一个指定的N场比赛的长度为N的单式投注字符串进行组合  * 输入单式投注注字符串string，例如31311133，组合得到类似******33,*****1*3,... ...结果的集合  *  * @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) {  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  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++;  }  ccupyIndexList.add(i);  }  }  // 根据起始startBitSet，构造带*的组合字符串并加入容器  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; // 统计遇到10后，左边0的个数  int oneCount = 0; // 统计遇到10后，左边1的个数  int pos = 0; // 记录当前遇到10的索引位置  char[] charArrayClone = this.charArray.clone();  // 遍历startBitSet来确定10出现的位置  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变为01  this.startBitSet.set(this.occupyIndexList.get(i), false);  this.startBitSet.set(this.occupyIndexList.get(i+1), true);  break;  }  }  // 将遇到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  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());  }  }

上述测试耗时大约2s左右。

上述算法实现主要是针对两种条件进行实现的，即：

***个是完全数字字符串 ——> 带有*号的组合数字字符串;

第二个带有*号的组合数字字符串 ——> 在该基础上继续组合得到带有*号的组合数字字符串。

如果使用上述算法实现处理***个条件，由于使用了列表List来记录索引，使执行速度略微低一点，比之于前面实现的不使用List列表来处理。

关于Java中怎么实现一个通用组合算法问题的解答就分享到这里了，希望以上内容可以对大家有一定的帮助，如果你还有很多疑惑没有解开，可以关注亿速云行业资讯频道了解更多相关知识。