分割文字列 – デカルトの方法

algorithm cartesian-product java split string

次のような文字列が与えられます。

" foo bar-baz-zzz "

値を保持しながら、文字 “”と ” – “で分割したいのですが、入力のすべての組み合わせを取得します。

を含む2次元配列を取得したい

{{"foo"、 "bar"、 "baz"、 "zzz"}、{"foo bar"、 "baz"、 "zzz"}、{"foo"、 "bar-baz"、 "zzz"}、 {"foo bar-baz"、 "zzz"}、{"foo"、 "bar"、 "baz-zzz"}、{"foo bar"、 "baz-zzz"}、{"foo"、 "bar-" baz-zzz "}、{" foo bar-baz-zzz "}}

このように文字列を分割するためのJavaの組み込みメソッドはありますか? たぶん、Apache Commonsのようなライブラリの中にありますか? それとも、forループの壁を書く必要がありますか?

  3  1


ベストアンサー

これが*働く*再帰的な解決策です。 私は物事を簡単にするために2次元配列ではなく `List>`を使いました。 コードは少し醜いので、おそらく少し片付けることができます。

出力例:

$ javaメインfoo bar-baz-zzz処理:foo bar-baz-zzz
[foo, bar, baz, zzz]
[foo, bar, baz-zzz]
[foo, bar-baz, zzz]
[foo, bar-baz-zzz]
[foo bar, baz, zzz]
[foo bar, baz-zzz]
[foo bar-baz, zzz]
[foo bar-baz-zzz]

コード:

import java.util。*;

public class Main {public static void main(String [] args){//最初にコマンドライン引数から単一の文字列を構築します。 StringBuilder sb = new StringBuilder();イテレータit = Arrays.asList(args).iterator(); while(it.hasNext()){sb.append(it.next());

if(it.hasNext()){sb.append( ''); }}

プロセス(sb.toString()); }

static static void process(String str){System.err.println( "Processing:" str);リスト>結果=新しいLinkedList>();

//魔法をかける再帰的メソッドを呼び出す。 プロセス(文字列、0、結果、新しいLinkedList()、新しいStringBuilder())。

(リスト結果:results){System.err.println(result); }}

protected static void process(String str、int pos、List> resultsSoFar、List currentResult、StringBuilder sb){if(pos == str.length()){//基本ケース:現在の結果にバッファの内容を追加する//そして現在の結果をresultsSoFarに追加する。 currentResult.add(sb.toString()); resultsSoFar.add(currentResult); } else {//ステップの場合:posの文字を調べてから再帰呼び出しを行います。 char c = str.charAt(pos);

if(c == '' || c == ' - '){// ''または ' - 'に遭遇した場合、2回再帰します。 //文字を区切り文字として扱う場合と//「通常の」文字として扱う場合。 リストコピー= new LinkedList(currentResult); copy.add(sb.toString());プロセス(文字列、位置1、resultsSoFar、コピー、新しいStringBuilder())。

sb.append(c);プロセス(str、pos 1、resultsSoFar、currentResult、sb); } else {sb.append(c);}プロセス(str、pos 1、resultsSoFar、currentResult、sb); }}}}

6


これは再帰的なスタイルで書かれたはるかに短いバージョンです。 Pythonでしか書けないことをお詫び申し上げます。 私はそれがどれほど簡潔であるのが好きです。きっとここにいる誰かがJavaバージョンを作ることができるでしょう。

def rec(h、t):len(t)<2の場合:[[ht]]を返します。 ]、t [1:])rec(ht [0]、t [1:])[rec( ''、t [1:])のxの[[h] x]を返す

そしてその結果:

>>> rec( ''、 "foo bar-baz-zzz")
[['foo bar-baz-zzz'], ['foo bar-baz', 'zzz'], ['foo bar', 'baz-zzz']
、['foo bar'、 'baz'、 'zzz']、['foo'、 'bar-baz-zzz']、['foo'、 'bar-baz'、 'zzz']、['foo' 、 'bar'、 'baz-zzz']、['foo'、 'bar'、 'baz'、 'zzz']]

4


これは分割値のリストを遅延して返すクラスです。

パブリッククラスSplitはIteratorを実装しています。プライベートファイナルパターンパターン。 private Stringサブシーケンス。プライベートファイナルマッチャーマッチャー。プライベートブール値done = false。プライベート最終文字列シーケンス。パブリック分割(パターンパターン、文字列シーケンス){this.pattern =パターン; matcher = pattern.matcher(sequence); this.sequence = sequence; }

@Override public list next(){if(done){新しいIllegalStateException()をスローします。 while(true){if(kid == null){if(matcher.find()){subsequence = sequence.substring(matcher.end());} kid = new Split(パターン、シーケンス文字列(0、matcher.start())); } else {break;} else {if(kid.hasNext()){List next = kid.next();}} next.add(サブシーケンス);次に戻る} else {kid = null; done = true;リストリスト= new ArrayList(); list.add(シーケンス);リストを返す。 public boolean hasNext(){return!done;} @Override publicブール値。 public void remove(){新しいUnsupportedOperationException()をスローします。 }}

(コードのフォーマットを許してください – それはネストされたスクロールバーを避けるためです)。

サンプル呼び出しの場合

パターンパターン= Pattern.compile( "|  - ");文字列str = "foo bar-baz-zzz";分割分割= new分割(パターン、文字列); while(split.hasNext()){System.out.println(split.next()); }

…​it will emit:

[foo, bar-baz-zzz]
[foo, bar, baz-zzz]
[foo bar, baz-zzz]
[foo, bar-baz, zzz]
[foo, bar, baz, zzz]
[foo bar, baz, zzz]
[foo bar-baz, zzz]
[foo bar-baz-zzz]

実装を改善することができると思います。

3


なぜあなたはそれが必要なのですか?

与えられたN個のトークンの文字列に対して、ca N * 2 ^ N個の文字列の配列を取得したいことに注意してください。 安全な方法で行わなければ、これは大量のメモリを消費する可能性があります。

たぶん、あなたはそれをすべて繰り返す必要があるでしょうね。 もしそうなら、元の文字列を保持して、あなたがそれを尋ねるたびに単にあなたに行を分割する異なる方法を与えるクラスを作成する方が良いです。 これにより、大量のメモリを節約し、スケーラビリティを向上させることができます。

1


ライブラリメソッドはありません。

そのためには、区切り文字を保存して文字列をトークン化し(この場合は ” – “を使用)、次に区切り文字をバイナリフラグに関連付けられているとみなし、フラグの値に基づいてすべての組み合わせを構築します。

あなたのケースでは、 “”、 ” – “、 ” – “の3つの区切り記号があるので、3つのバイナリフラグがあります。 文字列には2 ^ 3 = 8の値が入ります。

0


タイトルとURLをコピーしました