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;

public class CommonSplitter {

private int starCount;

private boolean duplicate;

private Collection filteredContainer;

public Collection getFilteredContainer() {

return filteredContainer;

}

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();

}

}

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开发的还看过

• Java程序语言通用组合算法的实现

本文标题：#Java程序语言通用组合算法的实现#，宏鹏发布于北大青鸟鲁广校区。Java实现通用组合算法，存在一个类似{31311133，33113330}这样的集合，经过8取5组合，其他位置用非字母数字字符替代，比如使用*号，得到类似{3***1133，***13330，... ...}这样的集合。