Найти все возможные поднаборы с заданной строкой

Question

Я пытаюсь найти все возможные анаграммы строки в Java. Под этим я подразумеваю, что если у меня есть длинное слово длиной 4 символа, я хочу, чтобы все возможные 3 символа длинных слов, полученных из него , все 2 символа длинны и все 1 символ длинный. Самый простой способ - использовать две вложенные петли и итерацию над строкой. Это мой код, как сейчас:

private ArrayList<String> subsets(String word){ 
     ArrayList<String> s = new ArrayList<String>(); 
     int length = word.length(); 
     for (int c=0; c<length; c++){ 
      for (int i=0; i<length-c; i++){ 
       String sub = word.substring(c, c+i+1); 
       System.out.println(sub); 
       //if (!s.contains(sub) && sub!=null) 
        s.add(sub); 
      } 
     } 
     //java.util.Collections.sort(s, new MyComparator()); 
     //System.out.println(s.toString()); 
     return s; 
    } 

Моя проблема заключается в том, что она работает на 3-х букв слова, fun yelds этот результат (не обращайте внимания на порядок, слово обрабатывается так, что у меня есть строка с буквы в алфавитном порядке):

f 
fn 
fnu 
n 
nu 
u 

Но когда я пытаюсь 4 букв слова, оно оставляет что-то, как и в catq дает мне:

a 
ac 
acq 
acqt 
c 
cq 
cqt 
q 
qt 
t 

т.е. я не s ee длинное слово длиной 3 символа act - это тот, который я ищу при тестировании этого метода. Я не могу понять, в чем проблема, и это, скорее всего, логическая ошибка, которую я создаю при создании подстрок. Если кто-нибудь может мне помочь, пожалуйста, не дайте мне код для этого, а скорее аргументы за ваше решение. Это часть курсовой работы, и я должен сам придумать код.

EDIT: чтобы очистить что-то, для меня ПОЛ, ККА, CAQ, AQC, ВКА ЧАС и т.д., то же самое - Для того, чтобы сделать его еще более очевидным, что происходит в том, что строка получает сортируются в алфавитном порядке порядок, поэтому все эти перестановки должны появиться как один уникальный результат, acq. Таким образом, мне не нужны все перестановки строки, а, скорее, с длинной строкой длиной 4 символа, все 3-символьные длинные, которые я могу извлечь из нее, - это означает, что выбирая по одному символу за раз и возвращая эту строку в результате чего это делается для каждого символа в исходной строке. Надеюсь, я поставил свою проблему немного яснее.

Answer 1

Это метод, который я придумал, кажется, что он работает

private void subsets(String word, ArrayList<String> subset){ 
     if(word.length() == 1){ 
      subset.add(word); 
      return; 
     } 
     else { 
      String firstChar = word.substring(0,1); 
      word = word.substring(1); 
      subsets(word, subset); 
      int size = subset.size(); 
      for (int i = 0; i < size; i++){ 
       String temp = firstChar + subset.get(i); 
       subset.add(temp); 
      } 
      subset.add(firstChar); 
      return; 
     } 
    } 

Что я могу сделать, это проверить, если это слово больше, чем один символ, в противном случае я буду добавлять символ в одиночку в ArrayList и начните рекурсивный процесс. Если он больше, я сохраняю первый символ и выполняю рекурсивный вызов с остальной частью String. Что происходит, так это то, что вся строка нарезается символами, сохраненными в рекурсивном стеке, до тех пор, пока я не попаду в точку, где мое слово стало длиной 1, осталось только один символ.

Когда это происходит, как я сказал в начале, персонаж добавляется в список, теперь начинается рекурсия, и он смотрит на размер массива, в первой итерации - 1, а затем с циклом for добавляет символ, сохраненный в стеке, для предыдущего вызова, связанного с каждым элементом в ArrayList. Затем он добавляет персонажа самостоятельно и снова разворачивает рекурсию. I.E., Со словом fun это происходит:

f saved 
List empty 
recursive call(un) 
- 
u saved 
List empty 
recursive call(n) 
- 
n.length == 1 
List = [n] 
return 
- 
list.size=1 
temp = u + list[0] 
List = [n, un] 
add the character saved in the stack on its own 
List = [n, un, u] 
return 
- 
list.size=3 
temp = f + list[0] 
List = [n, un, u, fn] 
temp = f + list[1] 
List = [n, un, u, fn, fun] 
temp = f + list[2] 
List = [n, un, u, fn, fun, fu] 
add the character saved in the stack on its own 
List = [n, un, u, fn, fun, fu, f] 
return 

Я был как можно более ясно, я надеюсь, что это проясняет, что моя первоначальная проблема и как ее решить.

Answer 2

Это прекрасно работает, вы просто ошибочно написали «caqt» как «acqt» в своих тестах/вводах.

(Вопрос, вероятно, что вы сортировка ввода Если вы хотите substrings, вы должны оставить вход НЕСОРТИРОВАННЫЙ.).

После ваших правок: см Generating all permutations of a given string Тогда просто сортировать отдельные буквы, и положить их в наборе.

Answer 3

Это рабочий код:

public static void main(String[] args) { 
    String input = "abcde"; 
    Set<String> returnList = permutations(input); 
    System.out.println(returnList); 
} 

private static Set<String> permutations(String input) { 
    if (input.length() == 1) { 
     Set<String> a = new TreeSet<>(); 
     a.add(input); 
     return a; 
    } 
    Set<String> returnSet = new TreeSet<>(); 

    for (int i = 0; i < input.length(); i++) { 
     String prefix = input.substring(i, i + 1); 
     Set<String> permutations = permutations(input.substring(i + 1)); 
     returnSet.add(prefix); 
     returnSet.addAll(permutations); 
     Iterator<String> it = permutations.iterator(); 
     while (it.hasNext()) { 
      returnSet.add(prefix + it.next()); 
     } 
    } 
    return returnSet; 
} 

Answer 4

Хорошо, как вы уже разработали свои собственные решения, я дам вам мой взгляд на него. Во-первых, рассмотрите, насколько велик ваш список результатов. Вы по сути принимаете каждую букву по очереди и включаете ее или нет. 2 возможности для каждой буквы, дает вам 2^n итоговых результатов, где n - количество букв. Это, конечно, включает случай, когда вы не используете какую-либо букву и заканчиваете пустой строкой.

Далее, если вы перечислить все возможности с 0 для «включить эту букву» и 1 для не включайте его, принимая свой «» FNU пример вы в конечном итоге с:

000 - '' 
001 - 'u' 
010 - 'n' 
011 - 'nu' 
100 - 'f' 
101 - 'fu' (no offense intended) 
110 - 'fn' 
111 - 'fnu'. 

Очевидно, это просто двоичные числа, и вы можете получить функцию, которая задает любое число из 0-7 и трехбуквенный ввод, будет вычислять соответствующее подмножество.

Это довольно легко сделать в Java .. нет Java компилятор под рукой, но это должно быть примерно правильно:

public string getSubSet(string input, int index) { 
    // Should check that index >=0 and < 2^input.length here. 
    // Should also check that input.length <= 31. 
    string returnValue = ""; 
    for (int i = 0; i < input.length; i++) { 
    if (i & (1 << i) != 0) // 1 << i is the equivalent of 2^i 
     returnValue += input[i]; 
    } 
    return returnValue; 
} 

Затем, если вам нужно, вы можете просто сделать цикл, вызывает эту функцию, например:

for (i = 1; i < (1 << input.length); i++) 
    getSubSet(input, i); // this doesn't do anything, but you can add it to a list, or output it as desired. 

Примечание Я начал с 1 вместо 0- это потому, что результат по индексу 0 будет пустая строка. Кстати, это на самом деле делает наименее значимый бит, поэтому ваш выходной список будет «f», «n», «fn», «u», «fu», «nu», «fnu», но порядок didn ' t кажутся важными.