Возврат не работает для печати всех комбинаций строки?

Я пытаюсь напечатать все перестановки строки. Но, несмотря на все мои усилия, я не могу получить требуемый результат для своего кода. Может кто-нибудь объяснить мне, что не так с моим кодом? Я пробовал это в течение многих часов и с треском провалился.

Вывод для приведенного ниже кода: -

азбука

Это функция перестановки для возврата: -

int i, l = 2;
void permute(String str, int n)
{
    for(i=n;i<=l;i++)
    {
        if(n==l)
        {
            System.out.println(swap(str,n,i));
            return;
        }
        else
            permute(swap(str,n,i),n+1);
    }
}

Это основная функция, которая запускает приведенный выше код:

public static void main(String args[])
{
    BacktrackTest bt=new BacktrackTest();
    String c="abc";
    bt.permute(c,0);
}

Это код для обмена: -

String swap(String st, int s1, int s2)
{
    char chr[] = st.toCharArray();
    char t;
    t = chr[s1];
    chr[s1] = chr[s2];
    chr[s2] = t;
    st = String.valueOf(chr);
    return st;
}

java dynamic-programming backtracking recursive-backtracking
person Rishi Swethan    schedule 07.12.2016    source источник
comment
Является ли это условие приращения в цикле for i++ таким, каким оно должно быть? Разве это не должно быть i--?   -  person Omoro    schedule 07.12.2016
comment
n будет начальным индексом строки, а l — конечным. Цикл проходит от n до l. Итак, это должно быть i++   -  person Rishi Swethan    schedule 07.12.2016
comment
Я попробовал ваш код, и он работает нормально. Он выводит abc acb bac bca cba cab для каждой перестановки в отдельной строке. Вы уверены, что код, который вы используете, совпадает с кодом в вашем вопросе? РЕДАКТИРОВАТЬ: мой плохой, я сделал небольшую модификацию при копировании, см. мой ответ.   -  person walen    schedule 07.12.2016
comment
Серьезно? Я удивлен! Как ты его запускал? Я запустил его в затмении   -  person Rishi Swethan    schedule 07.12.2016
comment
Это сработало. Глупая ошибка, как указано в ответе   -  person Rishi Swethan    schedule 07.12.2016

Ответы (1)


arrow_upward
0
arrow_downward

Не определяйте i вне метода permute. Попробуй это:

int l = 2;
void permute(String str, int n)
{
    for(int i=n;i<=l;i++)
    {
        if(n==l)
        {
            System.out.println(swap(str,n,i));
            return;
        }
        else
            permute(swap(str,n,i),n+1);
    }
}

Если вы объявляете i вне цикла for, его значение не "восстанавливается" для вызывающего после возврата.
В вашем примере, когда вы вводите if(n==l), значение i равно 2, но после return; оно по-прежнему равно 2. из-за его глобального охвата. Таким образом, на следующей итерации оно увеличивается до 3, поэтому i<=l оказывается ложным, и программа завершается.
Если вы объявите i внутри цикла, после того, как вы return;, оно вернется к 1, чтобы цикл мог продолжаться.

person walen    schedule 07.12.2016
comment
Не могли бы вы подсказать, почему это проблема? - person Rishi Swethan; 07.12.2016
comment
Да, просто добавил объяснение. - person walen; 07.12.2016
comment
Думаю, я понял. i когда снаружи будет иметь значение уже при одной итерации, а потом при рекурсивном вызове функции происходит конфликт. Верно? - person Rishi Swethan; 07.12.2016
comment
Точно, ты понял :) - person walen; 07.12.2016