Split String - декартов способ

Question

Учитывая следующую строку:

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

Есть ли встроенный метод в Java, чтобы разбить строку таким образом? Может быть, в библиотеке, подобной Apache? Или мне нужно написать стену для петель?

Answer 1

Метода библиотеки нет.

Для этого вам необходимо подделать строку (в вашем случае с помощью «-»), сохранив разделители, а затем вы должны подумать о разделителях, связанных с бинарными флагами, и построить все комбинации на основе значения флагов ,

В вашем случае у вас есть 3 разделителя: «", "-" и "-", поэтому у вас есть 3 бинарных флага. В строке вы получите 2^3 = 8 значений.

Answer 2

Рекурсивное решение, которое работает. Я использовал List<List<String>>, а не 2-мерный массив, чтобы сделать вещи проще. Код немного уродливый и, вероятно, можно немного подобрать. Выход

Пример:

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

Код:

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

Зачем вам это?

Обратите внимание, что для заданной строки из N токенов вы хотите получить массив строк N * 2^N. Это (может) потреблять тонны памяти, если это не сделано безопасным способом ...

Я предполагаю, что вам, вероятно, понадобится повторить все это, не так ли? Если это так, то лучше создать какой-то класс, который сохранит исходную строку и просто даст вам разные способы разделения строки каждый раз, когда вы ее попросите. Таким образом вы сэкономите массу памяти и получите лучшую масштабируемость.

Answer 4

Вот это класс, который будет лениво возвращать списки значений расщепленных:

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

(простите форматирование кода - это, чтобы избежать вложенных скроллбары).

Для образца вызова:

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

... он будет испускать:

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

Я представляю себе реализацию можно улучшить.

Answer 5

Вот более короткая версия, написанная в рекурсивном стиле. Я прошу прощения за то, что я могу написать его только на Python. Мне нравится, насколько он лаконичен; конечно, кто-то здесь сможет сделать версию Java.

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:])] 

и результат:

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