Split String - der cartesianischen Weg

Question

die folgende Zeichenfolge Gegeben:

"foo bar-baz-zzz"

Ich möchte es an den Zeichen spalten „“ und „-“, dessen Wert erhalten, sondern alle Kombinationen von Eingaben zu erhalten.

i

{{"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"}} 

Gibt es eine integrierte Methode in Java, die ein zweidimensionales Array erhalten möchten die Zeichenfolge auf diese Weise zu spalten? Vielleicht in einer Bibliothek wie Apache Commons? Oder muss ich eine Wand aus For-Schleifen schreiben?

Answer 1

Es gibt keine Bibliotheksmethode.

Um dies zu erreichen, sollten Sie die Zeichenkette (in Ihrem Fall mit "-") durch Beibehaltung der Trennzeichen in Token zerlegen, und dann sollten Sie Separatoren als binäre Flags betrachten und alle Kombinationen basierend auf dem Wert der Flags erstellen .

In Ihrem Fall haben Sie 3 Trennzeichen: "", "-" und "-", also haben Sie 3 binäre Flags. Sie erhalten am Ende 2^3 = 8 Werte in der Zeichenfolge.

Answer 2

Hier ist eine rekursive Lösung, die funktioniert. Ich habe ein List<List<String>> anstatt ein 2-dimensionales Array verwendet, um die Dinge einfacher zu machen. Der Code ist ein bisschen hässlich und könnte wahrscheinlich ein wenig aufgeräumt werden.

Beispielausgabe:

$ java Main foo bar-baz-zzz 
Processing: 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] 

Code:

import java.util.*; 

public class Main { 
    public static void main(String[] args) { 
    // First build a single string from the command line args. 
    StringBuilder sb = new StringBuilder(); 
    Iterator<String> it = Arrays.asList(args).iterator(); 
    while (it.hasNext()) { 
     sb.append(it.next()); 

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

    process(sb.toString()); 
    } 

    protected static void process(String str) { 
    System.err.println("Processing: " + str); 
    List<List<String>> results = new LinkedList<List<String>>(); 

    // Invoke the recursive method that does the magic. 
    process(str, 0, results, new LinkedList<String>(), new StringBuilder()); 

    for (List<String> result : results) { 
     System.err.println(result); 
    } 
    } 

    protected static void process(String str, int pos, List<List<String>> resultsSoFar, List<String> currentResult, StringBuilder sb) { 
    if (pos == str.length()) { 
     // Base case: Reached end of string so add buffer contents to current result 
     // and add current result to resultsSoFar. 
     currentResult.add(sb.toString()); 
     resultsSoFar.add(currentResult); 
    } else { 
     // Step case: Inspect character at pos and then make recursive call. 
     char c = str.charAt(pos); 

     if (c == ' ' || c == '-') { 
     // When we encounter a ' ' or '-' we recurse twice; once where we treat 
     // the character as a delimiter and once where we treat it as a 'normal' 
     // character. 
     List<String> copy = new LinkedList<String>(currentResult); 
     copy.add(sb.toString()); 
     process(str, pos + 1, resultsSoFar, copy, new StringBuilder()); 

     sb.append(c); 
     process(str, pos + 1, resultsSoFar, currentResult, sb); 
     } else { 
     sb.append(c); 
     process(str, pos + 1, resultsSoFar, currentResult, sb); 
     } 
    } 
    } 
} 

Answer 3

Warum Sie das brauchen?

Beachten Sie, dass Sie für eine gegebene Zeichenfolge von N Token ein Array von ca N * 2^N Zeichenfolgen erhalten möchten. Dies kann Tonnen von Speicher verbrauchen, wenn es nicht in einer sicheren Weise getan wird ...

Ich denke, dass Sie wahrscheinlich müssen durchlaufen alles, oder? Wenn dem so ist, ist es besser, eine Klasse zu erstellen, die die ursprüngliche Zeichenkette behält und Ihnen einfach verschiedene Möglichkeiten gibt, eine Zeile bei jeder Frage aufzuteilen. Auf diese Weise sparen Sie viel Speicherplatz und erhalten eine bessere Skalierbarkeit.

Answer 4

Hier ist eine Klasse, die träge Listen von Split Werte zurück:

public class Split implements Iterator<List<String>> { 
    private Split kid;     private final Pattern pattern; 
    private String subsequence;  private final Matcher matcher; 
    private boolean done = false;  private final String sequence; 
    public Split(Pattern pattern, String sequence) { 
    this.pattern = pattern;   matcher = pattern.matcher(sequence); 
    this.sequence = sequence; 
    } 

    @Override public List<String> next() { 
    if (done) { throw new IllegalStateException(); } 
    while (true) { 
     if (kid == null) { 
     if (matcher.find()) { 
      subsequence = sequence.substring(matcher.end()); 
      kid = new Split(pattern, sequence.substring(0, matcher.start())); 
     } else { break; } 
     } else { 
     if (kid.hasNext()) { 
      List<String> next = kid.next(); 
      next.add(subsequence); 
      return next; 
     } else { kid = null; } 
     } 
    } 
    done = true; 
    List<String> list = new ArrayList<String>(); 
    list.add(sequence); 
    return list; 
    } 
    @Override public boolean hasNext() { return !done; } 
    @Override public void remove() { throw new UnsupportedOperationException(); } 
} 

(die Code-Formatierung Vergib - es ist verschachtelte Bildlaufleisten zu vermeiden).

Für das Beispielaufruf:

Pattern pattern = Pattern.compile(" |-"); 
String str = "foo bar-baz-zzz"; 
Split split = new Split(pattern, str); 
while (split.hasNext()) { 
    System.out.println(split.next()); 
} 

... es wird emittieren:

[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] 

ich die Implementierung vorstellen, verbessert werden könnte, auf.

Answer 5

Hier ist eine viel kürzere Version, in einem rekursiven Stil geschrieben. Ich entschuldige mich dafür, dass ich es nur in Python schreiben konnte. Ich mag es, wie knapp es ist; sicherlich wird hier jemand eine Java-Version machen können.

def rec(h,t): 
    if len(t)<2: return [[h+t]] 
    if (t[0]!=' ' and t[0]!='-'): return rec(h+t[0], t[1:]) 
    return rec(h+t[0], t[1:]) + [ [h]+x for x in rec('',t[1:])] 

und das Ergebnis:

 
>>> 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']]