Anagram Algorithm Уточнение

Question

Я новичок в этом форуме и хотел задать вопрос. Я видел нескольких людей, задающих вопросы по анаграммам, но мой вопрос связан с этим конкретным алгоритмом. Я видел этот алгоритм, который использует метод рекурсии для генерации анаграмм, но часть этого алгоритма мне не очень понятна. Я хотел обратиться за помощью с точки зрения того, почему этот конкретный шаг сделан. Этот алгоритм изложено в разделе «Опрос по программированию». Вот алгоритм:

Если вы мимо последней позиции
      печать строки и возврата
В противном случае
      Для каждой буквы в строке ввода
            Если оно отмечено, перейдите к следующей букве
            Else разместить письмо в текущей позиции
      - Марк письмо используется
      - переставить оставшиеся буквы уставившись в текущей позиции + 1
      - Отметить письмо как неиспользуемый

Вот этот код для этого же:

void permute(String str){ 
    int length = str.length(); 
    boolean[] used = new boolean[length]; 
    StringBuffer out = new StringBuffer(); 
    char[] in = str.toCharArray(); 
    doPermute(in, out, used, length, 0); 
} 
void doPermute(char[] in, StringBuffer out, boolean[] used, int length, 
    int level){ 
    if (level == length){ 
     System.out.println(out.toString()); 
     return; 
    } 
    for (int i = 0; i<length; i++){ 
     if (used[i]) continue; 
     out.append(in[i]); 
     used[i] = true; 
     doPermute(in, out, used, length, level + 1); 
     used[i] = false; 
     out.setLength(out.length() - 1); // why are we reducing the size of out?? 
    } 
} 

В пояснении кода указано, что при возврате рекурсивного вызова последний символ просто отбрасывается путем уменьшения размера буфера. Я не могу понять, почему мы бросаем последнего персонажа? Может ли кто-нибудь помочь. Благодаря!!!!!

Answer 1

Чтобы вернуть эффект out.append(in[i]); (который добавляет символ) и восстановить буфер до того же состояния после каждой итерации цикла for.

for (int i = 0; i<length; i++){ 
    if (used[i]) continue; 
    out.append(in[i]); // try adding the ith letter 
    used[i] = true; // and mark it as used 
    doPermute(in, out, used, length, level + 1); // do all the permutations for the remaining letters 
    used[i] = false;     // undo what we did 
    out.setLength(out.length() - 1); // at the start of the loop 
} 

Это так просто.

Answer 2

алгоритм делает следующее:

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

Так давайте есть пример здесь:

Мы имеем следующее письмо:

е, х, а, т, р, л, е

Позволяет выбрать первая буква:

его либо:

• e и один из возможных перестановок xample,
• x и один из возможных перестановок eample
• т.д.

Когда мы подберем все кожанные мы напечатаем слово создали.

Вы также можете подумать об этом как о дереве решений, Сначала вы выбираете одну из n букв, затем выбираете одну из оставшихся и после того, как вы выбрали все из них (вы попали в нижнюю часть дерева и получили самостоятельно одна из уникальных анаграмм), потому что на каждом шаге у вас есть цикл for (так что для всех возможных решений исследуйте нижние уровни дерева) вы получите каждую комбинацию и распечатаете ее.

Я действительно надеюсь, что это поможет.