Предполагая, что вы определили, что вам действительно нужно (все подмножества, отсортированные как исходный список), вы можете сделать это, думая об этом как об этом и используя эти свойства:

• отсортировано как в вашем списке
• конечный
• делимый

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

итеративное решение

Подумайте о возможных битовых состояниях. У вас есть n символов, и вы назначаете каждому символу бит (в вашем случае 4). Затем каждое возможное битовое состояние определяет допустимую перестановку подмножества, например. для {A, B, C, G}:

1001 будет AG

Как мы знаем, все возможные состояния битового набора являются «счетными», или, другими словами, вы можете просто пересчитать их, считая от наименьшего состояния к наибольшему, добавляя 1.

Сделайте цикл, считая от 1 до 2 ^ n - 1 (где n - количество имеющихся у вас символов), а затем создайте свой String, добавив (в правильной последовательности) все символы, для которых у вас есть 1 в качестве их представляющего бита, и опустите символы с 0. Затем вы «пересчитываете» все возможные допустимые перестановки.

Такая реализация сильно зависит от программиста и его стиля, но для меня это выглядело бы примерно так:

public static List<String> associationRules(List<String> elements) {
  List<String> result = new ArrayList<>();
  long limit = 1 << elements.size(); // thanks to saka1029 for this correction. My code was n^2 not 2^n.

  // count from 1 to n^2 - 1
  for (long i = 1; i < limit; ++i) {
    StringBuilder seq = new StringBuilder();

    // for each position (character) decide, whether to include it based on the state of the bit.
    for (int pos = 0; pos < elements.size(); ++pos) {
      boolean include = ((i >> pos) % 2) == 1; // this line will give you true, if the in 'i' the bit at 'pos' (from behind) is 1, and false otherwise.
      if (include) {
        seq.append(elements.get(pos));
      }
    }

    // add to the final result the newly generated String.
    result.add(seq.toString());
  }

  return result;
}

и результат выглядит так: [A, B, AB, C, AC, BC, ABC, G, AG, BG, ABG, CG, ACG, BCG, ABCG]

Это итеративное (нерекурсивное) решение, но есть и рекурсивное, которое может (или не может) быть проще в реализации.

рекурсивное решение

Рекурсивное решение может просто работать, создавая метод, который принимает в качестве аргументов набор отсортированных символов и логическое состояние (включено или не включено) и возвращает список всех возможных отсортированных подперестановок. Затем вы должны вызвать это с помощью общедоступного метода, который передает символы и 0 в качестве позиции и либо true, либо false в качестве начального состояния (другое появится позже).

Затем метод работает по схеме «разделяй и властвуй». Вы включаете символ в определенную позицию (в зависимости от того, установлен ли флаг включения) и снова вызываете собственный метод с клонированным (под)набором символов, который не включает первый символ.

Предположим на данный момент, что вы начинаете с того, что не включаете первый символ каждой последовательности (но позже включаете его). Если вы передадите такому методу набор символов {A, B, C, G}, тогда метод (запустится) будет работать следующим образом:

A: recurse on {B, C, G}
  B: recurse on {C, G}
    C: recurse on {G}
      G: set is empty,
      G: Add to the result all Strings with 'G' prefixed and without.
      G: return {"G", ""}
    C: Add to the result all Strings with 'C' prefixed and without.
    C: {"CG", "C", "G", ""}
    ...

Таким образом, вы будете рекурсивно собирать все отсортированные подмножества перестановок. В зависимости от того, разрешена ли пустая строка, вы можете удалить ее в конце или вообще не добавлять.

Я реализовал это так, но есть и другие правильные способы:

public static List<String> associationRules2(List<String> elements) {
    List<String> result = new ArrayList<>();
    String thisElement = elements.get(0);
    
    // build the subset list (leaving out the first element
    List<String> remaining = new ArrayList<>();
    boolean first = true;
    for (String s : elements) {
        if (first) {
            first = false;
        } else {
            remaining.add(s);
        }
    }
    
    // if the subset is not empty, we recurse.
    if (! remaining.isEmpty()) {
        List<String> subPermutations = associationRules2(remaining);
        
        // add all permutations without thisElement.
        result.addAll(subPermutations);
        
        // add all permutations *with* thisElement.
        for (String s : subPermutations) {
            result.add(thisElement + s);
        }
    }
    
    // finally add thisElement on it's own.
    result.add(thisElement);
    
    return result;
}

Результат: [G, CG, C, BG, BCG, BC, B, AG, ACG, AC, ABG, ABCG, ABC, AB, A]