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);
-
- int count = 0;
- for (int i=0; i
- if(charArray[i] != '*') {
- if(count < starCount) {
- this.startBitSet.set(i, true);
- count++;
- }
- occupyIndexList.add(i);
- }
- }
-
- 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);
- }
- }
-
- 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;
- int oneCount = 0;
- int pos = 0;
- char[] charArrayClone = this.charArray.clone();
-
- 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;
-
- this.startBitSet.set(this.occupyIndexList.get(i), false);
- this.startBitSet.set(this.occupyIndexList.get(i+1), true);
- break;
- }
- }
-
- 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);
- }
- }}
-
- for (int i=0; i
- if (this.startBitSet.get(this.occupyIndexList.get(i))) {
- charArrayClone[this.occupyIndexList.get(i)] = '*';
- }
- }
- this.container.add(new String(charArrayClone));
- }
- }}}
|