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 Commons? Или я должен написать стену для петель?

Answer 1

Вот рекурсивное решение, которое работает . Я использовал 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 2

Вот гораздо более короткая версия, написанная в рекурсивном стиле. Я извиняюсь за то, что смог написать только на 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']]

Answer 3

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

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 4

Зачем вам это нужно?

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

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

Answer 5

Нет библиотечного метода.

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

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