Javaは一般的な組み合わせアルゴリズムを実装する

Java は一般的な組み合わせアルゴリズムを実装しています。{31311133,33113330} のようなセットがあります。5 つの組み合わせのうち 8 つが終わると、他の位置は * などの英数字以外の文字に置き換えられ、{3***1133,***13330,... ...} のようなセットが得られます。

現在、次のような需要があります。

{31311133,33113330} のようなセットがあります。8 個中 5 個以降は、他の位置が * などの英数字以外の文字に置き換えられ、{3***1133,***13330,... ...} のようなセットになります。

また、{3***1133,***13330} のようなセットの場合、5 つの組み合わせのうち 3 つを再度取得し、他の位置を * などを使用して英数字以外の文字に置き換えて、{*****133,*****330,3***1*3*,... ...} のようなセットを取得する必要があります。

このような要件に対する実装のアイデアは次のとおりです。

まず、主なアイデアは情報エンコードの原理に基づいています。文字列をスキャンすると、10 の組み合わせが 01 の組み合わせに変更されます。

次に、数値文字列ごとに 1 つのスレッドを設定し、その単一スレッド クラスにリストを設定して、処理対象の数値文字列 (* が含まれる場合も含まれない場合もあります) 内の各数値 (* ではない) のインデックス位置値を格納します。

ここでも、各位置が * に置き換えられて新しい結合文字列が取得されるかどうかをマークするように BitSet を設定します。

***、処理対象となる元のデジタル文字列をスキャンするプロセスでは、設定された文字リスト List 内のインデックスに従って BitSet が操作され、BitSet ごとに新しい組み合わせが得られます。

Java言語を使用した実装は次のとおりです。

パッケージorg.shirdrn;
 java.util.ArrayListをインポートします。
 java.util.BitSetをインポートします。
 java.util.Collectionをインポートします。
 java.util.Collectionsをインポートします。
 java.util.HashSetをインポートします。
 java.util.Iteratorをインポートします。
 java.util.Listをインポートします。
 /**
 * 一般的な組み合わせ分割クラス（単一スレッドベース）
 * 2 つの機能を実行できます。
 * *** を使用すると、完全な数値文字列を * を含む文字列に分割できます。
 * たとえば、コレクション {31311133,33113330} を入力すると、Splitter クラスはコレクションを走査し、各文字列に対して SplitterThread を作成します。
 * スレッドを使用して処理します。2-out-of-1 の組み合わせ、つまり starCount=8-2=6 の場合、スレッド処理では *******33、*****1*3 などの結果が得られます。
 * 次に、文字列を分割してフィルタリングした後に得られた文字列セット内の各文字列を * で結合します。
 * 例: セット 5 を入力し、1 を取ると、文字列セット {3***1133,***113330} が結合されます。
 * CommonSplitterクラスはコレクションを走査し、各文字列に対してSplitterThreadを作成します。
 * スレッド処理、2 in 1 の組み合わせ、つまり starCount=8-3-2=3 の場合、スレッド処理後の結果は *******33、*****1*3 などと同様になります。
 * @author 石 延軍
*/  
公共 クラスCommonSplitter {
プライベート 星の数を整数で表します。
プライベート ブール値の重複;
プライベートコレクションfilteredContainer;
パブリックコレクション getFilteredContainer() {
フィルターされたコンテナを返します。
 }
 /**
 * Splitterインスタンスを構築する
* @param コンテナ 処理される入力文字列コレクション
* @param starCount 長さNの数値文字列に対してMの組み合わせが実行される場合（つまり、NがMを取る場合）、starCount=NM
 * @param duplicate 重複を削除するかどうか
*/  
パブリックCommonSplitter(コレクション コンテナ、 int starCount、 boolean重複) {
 this .duplicate = 重複;
 .starCount = starCount;です。
 if ( this .duplicate) { // 重複を指定するかどうかに基づいてコンテナを作成する 
フィルターコンテナ = Collections.synchronizedSet(新しいHashSet());
 }
それ以外{
フィルターコンテナ = Collections.synchronizedList(新しいArrayList());
 }
イテレータ it = container.iterator();
 (it.hasNext())の間{
新しいスレッド(新しいSplitterThread(it.next().trim())).start();
 }
試す{
スレッド.スリープ( 50 );
 }キャッチ(InterruptedException e) {
 e.printStackTrace();
 }
 }
 /**
 * 指定されたNゲームの長さNの単一の賭け文字列を組み合わせる
* 31311133 などの単一の賭け文字列を入力し、それらを組み合わせて、*****33、*****1*3、... のような結果のセットを取得します。
 *
 * @author 石 延軍
*/  
クラスSplitterThreadはRunnableを実装します{
プライベート  char [] char配列;
プライベート  int len; // 数字の文字数 
 List occupyIndexList = new ArrayList(); // 文字列内の * のない位置のインデックスを数える 
プライベートリストコンテナ =新しいArrayList();
 private BitSet startBitSet; //ビットセットの開始状態 
 private BitSet endBitSet; // ループを制御するために使用されるビットセット終了状態 
パブリックスプリッタースレッド(文字列文字列) {
これは.charArray = string.toCharArray() です。
 this .len = string.replace( "*" , "" ).length();
 this .startBitSet = new BitSet(len);
 this .endBitSet = new BitSet(len);
 // startBitSet を初期化し、左側を * 記号で埋めます 
 intカウント = 0 ; //  
 ( int i = 0 ; iの場合
charArray[i] != '*'の場合{
カウント < スターカウントの場合
これを.startBitSet.set(i, true );
カウント++;
 }
占有インデックスリストを追加します(i);
 }
 }
 // endBit を初期化し、右側を * 記号で埋めます 
カウント = 0 ;
 ( int i = string.length()- 1 ; i > 0 ; i--) {
 charArray[i] != '*'の場合{
カウント < スターカウントの場合
これを.endBitSet.set(i, true );
カウント++;
 }
 ccupyIndexList.add(i);
 }
 }
 // 開始startBitSetに従って、*で結合された文字列を構築し、コンテナに追加します 
 char [] charArrayClone = this .charArray.clone();
 ( int i = 0 ; iの場合
if ( this .startBitSet.get(i)) {
 charArrayClone[i] = '*' ;
 }
 }
これを.container.add(新しいString(charArrayClone) );
 }
公共  void実行() {
これは.split();
同期された（フィルターされたコンテナ）{
フィルターされたコンテナ.addAll(この.コンテナ);
 }}
公共  void分割() {
 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 が現れる場所を特定します 
 ( int i = 0 ; iの場合
if (! this .startBitSet.get( this .occupyIndexList.get(i))) {
ゼロカウント++;
 }
 if ( this .startBitSet.get( this .occupyIndexList.get(i))
 && ! this .startBitSet.get( this .occupyIndexList.get(i+ 1 ))) {
位置 = i;
 1 カウント = i - ゼロカウント;
 // 10を01に変更 
 this .startBitSet.set( this .occupyIndexList.get(i), false );
 this .startBitSet.set( this .occupyIndexList.get(i+ 1 ), true );
壊す;
 }
 }
 // 10 に遭遇したら、左側にあるすべての 1 を左端に移動します 
 int count = Math.min(zeroCount, oneCount);
 int startIndex = this .occupyIndexList.get( 0 );
 int終了インデックス = 0 ;
位置が1 かつカウントが0の場合
pos--;
 endIndex = this .occupyIndexList.get(pos);
 ( int i = 0 ; iの場合
これを.startBitSet.set(startIndex, true );
これを.startBitSet.set(endIndex, false );
 startIndex = this .occupyIndexList.get(i + 1 );
 pos--;
 （位置> 0 ）の場合{
 endIndex = this .occupyIndexList.get(pos);
 }
 }}
 // 1 に遭遇した位置を * に置き換えます 
 ( int i = 0 ; iの場合
if ( this .startBitSet.get( this .occupyIndexList.get(i))) {
 charArrayClone[ this .occupyIndexList.get(i)] = '*' ;
 }
 }
これを.container.add(新しいString(charArrayClone) );
 }
 }}}

#p#

テストケースは次のとおりです。

パッケージorg.shirdrn;
 java.util.ArrayListをインポートします。
 java.util.Collectionをインポートします。
 junit.framework.TestCaseをインポートします。
 org.shirdrn.util.GoodToolsをインポートします。
公共 クラスTestCommonSplitter はTestCaseを拡張します{
プライベートCommonSplitter スプリッター;
公共  void setSplitter(コレクションコンテナ、 int starCount、 boolean duplicate) {
 this .splitter = new CommonSplitter(container, starCount, duplicate);
 }
公共  void testSplitter() {
コレクションコンテナー = new ArrayList();
コンテナを追加します( "1*10**" );
スターカウント= 2 ;
ブール値の重複 = true ;
 this .setSplitter(コンテナ、starCount、複製);
 System.out.println(この.splitter.getFilteredContainer());
 }
公共  void testSplitter3() {
コレクションコンテナー = new ArrayList();
コンテナを追加します( "1*10*1300*" );
スターカウント= 3 ;
ブール値の重複 = true ;
 this .setSplitter(コンテナ、starCount、複製);
 System.out.println(この.splitter.getFilteredContainer());
 assertEquals( 35 、この.splitter.getFilteredContainer().size());
 }
公共  void testNoStar() {
コレクションコンテナー = new ArrayList();
コンテナを追加します( "3110330" );
スターカウント= 3 ;
ブール値の重複 = true ;
 this .setSplitter(コンテナ、starCount、複製);
 System.out.println(この.splitter.getFilteredContainer());
 assertEquals( 35 、この.splitter.getFilteredContainer().size());
 }
公共  void testSplitter_8_310() {
 // 8ゲーム: 310  
文字列 multiSeq = "310,310,310,310,310,310,310,310" ;
コレクション コンテナー = GoodTools.getNSingleList(multiSeq);
 assertEquals( 6561 , コンテナのサイズ());
スターカウント= 4 ;
ブール値の重複 = false ;
 this .setSplitter(コンテナ、starCount、複製);
 assertEquals( 459270 、この.splitter.getFilteredContainer().size());
 }
 }

上記のテストには約 2 秒かかります。

上記のアルゴリズムは、主に次の 2 つの条件に対して実装されます。

*** は完全な数値文字列です -> * を含む結合された数値文字列です。

アスタリスクが付いた 2 番目の結合デジタル文字列 --> これを基に結合を続行して、アスタリスクが付いた結合デジタル文字列を取得します。

上記のアルゴリズムを使用して最初の条件を処理する場合、リストを使用してインデックスを記録するため、リストを使用せずに処理する以前の実装と比較して、実行速度がわずかに低下します。

【編集者のおすすめ】

1. Java オブジェクト インスタンスはいつ作成されますか?
2. Javaプログラミングを学ぶ8つのメリット
3. Java マルチスレッド プログラミングの詳細な分析
4. 開発者が犯す最も一般的な JavaScript の間違い 13 個