Как получить все возможные комбинации подстрок?

Question

У меня есть строка следующей структуры: A1 (N1, N2, N3) P4 (O3, O5) Y1.

Как получить все комбинации? Правило заключается в том, что параметры внутри скобок не должны совпадать. Для этого примера выход должен быть:

A1N1P4O3Y1, 
A1N2P4O3Y1, 
A1N3P4O3Y1, 
A1N1P4O5Y1, 
A1N2P4O5Y1, 
A1N3P4O5Y1. 

Может быть скобка, но она может быть без нее. Другой пример:

N3P5 (L1, L2) Q1, вывод должен быть:

N3P5L1Q1, 
N3P5L2Q1. 

Любой человек, элегантное решение?

Answer 1

Основная идея состоит в том, чтобы преобразовать строковый ввод в StringTemplate, который содержит части, которые могут быть одной строкой или группой строк.

Для каждой части создается итератор. Хотя некоторые итераторы могут идти дальше, обновите строковый массив, который содержит текущие значения компонентов и сбросит все итераторы частей, которые появляются перед измененной частью. Не стесняйтесь очищать повторяющийся код и при необходимости добавлять поддержку вложенных групп и проверку синтаксиса.

private static StringTemplate parse(String string) { 

    List<StringPart> parts = new ArrayList<StringPart>(); 

    boolean insideGroup = false; 
    StringBuilder currentToken = new StringBuilder(); 

    List<LiteralPart> groupParts = new ArrayList<LiteralPart>(); 

    for (int i = 0; i < string.length(); i++) { 
     char ch = string.charAt(i); 

     if (ch == '(') { 

      if (currentToken.length() != 0) { 
       parts.add(new LiteralPart(currentToken.toString())); 
       currentToken.delete(0, currentToken.length()); 
      } 

      insideGroup = true; 

     } else if (ch == ')') { 

      if (insideGroup) { 

       if (currentToken.length() != 0) { 
        groupParts.add(new LiteralPart(currentToken.toString())); 
        currentToken.delete(0, currentToken.length()); 
       } 

       parts.add(new CompositePart(groupParts)); 
       groupParts.clear(); 
       insideGroup = false; 

      } else { 
       currentToken.append(ch); 
      } 

     } else if (ch == ',') { 

      if (insideGroup) { 

       if (currentToken.length() != 0) { 
        groupParts.add(new LiteralPart(currentToken.toString())); 
        currentToken.delete(0, currentToken.length()); 
       } 

      } else { 
       currentToken.append(ch); 
      } 

     } else { 
      currentToken.append(ch); 
     } 
    } 

    if (currentToken.length() != 0) { 
     parts.add(new LiteralPart(currentToken.toString())); 
     currentToken.delete(0, currentToken.length()); 
    } 

    return new StringTemplate(parts); 

} 

private static final class StringTemplate { 

    private final List<StringPart> parts; 

    public StringTemplate(List<StringPart> parts) { 
     this.parts = parts; 
    } 

    public List<String> getCombinations() { 
     List<Iterator<String>> iterators = new ArrayList<Iterator<String>>(parts.size()); 

     for (StringPart part : parts) { 
      iterators.add(part.getStrings().iterator()); 
     } 

     String[] toJoin = new String[iterators.size()]; 

     List<String> combinations = new ArrayList<String>(); 
     int iteratorThatAdvanced; 
     int maxIteratorThatAdvanced = Integer.MIN_VALUE; 
     boolean first = true; 

     for (;;) { 

      iteratorThatAdvanced = -1; 

      for (int i = 0; i < iterators.size(); i++) { 
       Iterator<String> iterator = iterators.get(i); 

       if (first || iterator.hasNext()) { 
        String value = iterator.next(); 
        toJoin[i] = value; 

        iteratorThatAdvanced = i; 

        if (!first && i >= maxIteratorThatAdvanced) { 
         maxIteratorThatAdvanced = i; 
         break; 
        } 
       } 
      } 

      if (iteratorThatAdvanced < 0) { 
       break; 
      } 

      if (!first) { 
       for (int i = 0; i < iteratorThatAdvanced; i++) { 
        Iterator<String> iterator = parts.get(i).getStrings().iterator(); 
        iterators.set(i, iterator); 
        toJoin[i] = iterator.next(); 
       } 
      } 

      combinations.add(join(toJoin)); 
      first = false; 

     } 

     return combinations; 
    } 

} 

private static String join(String[] strings) { 
    StringBuilder builder = new StringBuilder(); 
    for (String string : strings) { 
     builder.append(string); 
    } 
    return builder.toString(); 
} 

private static abstract class StringPart { 

    abstract List<String> getStrings(); 

} 

private static final class LiteralPart extends StringPart { 

    private final String literal; 

    public LiteralPart(String literal) { 
     this.literal = literal; 
    } 

    @Override 
    List<String> getStrings() { 
     return Collections.singletonList(literal); 
    } 

} 

private static final class CompositePart extends StringPart { 

    private final List<LiteralPart> parts; 

    public CompositePart(List<LiteralPart> parts) { 
     this.parts = new ArrayList<LiteralPart>(parts); 
    } 

    @Override 
    List<String> getStrings() { 
     List<String> strings = new ArrayList<String>(parts.size()); 

     for (LiteralPart part : parts) { 
      strings.add(part.literal); 
     } 

     return strings; 
    } 

} 

Пример:

public static void main(String[] args) { 
    StringTemplate template = parse("A1(N1,N2,N3)P4(O3,O5)Y1"); 

    for (String combination : template.getCombinations()) { 
     System.out.println(combination); 
    } 

    template = parse("N3P5(L1,L2)Q1"); 

    for (String combination : template.getCombinations()) { 
     System.out.println(combination); 
    } 
}