Когда происходит приращение цикла for в этой рекурсивной функции?

Question

Ручная трассировка рекурсивных функций

В приведенном выше вопросе с утвержденным ответом кажется, что

void string_permutation(string str, int mid, int end)
{
    if (mid == end) 
        cout << str << endl;
    else 
    {
        for (int i = mid; i <= end; i++) 
        {
            swap(str[mid], str[i]);
            string_permutation(str, mid + 1, end);
            swap(str[mid], str[i]);
        }
    }
}

Допустим, мы пытаемся выполнить следующее: ("abcd", 0, 3)

В соответствии с ответом, данным ранее, "bacd" - это первое, на что изменяется строка, во время первого рекурсивного вызова (второго вызова функции), поэтому первый вызов + первый рекурсивный вызов выглядит следующим образом:

("abcd", 0, 3)
("bacd", 1, 3)

Однако, когда меня учили циклу for, было сказано, что содержимое цикла for выполняется до приращения (изменения индекса).

Что бы это значило, это то, что перед первым рекурсивным вызовом у нас есть int i = mid, это означает mid == 0 и i == 0, поэтому перестановка, происходящая непосредственно перед первым рекурсивным вызовом, такова: swap(str[0], str[0]);, что означает, что str, переданный рекурсивному вызову, по-прежнему ("abcd", 1, 3), по-прежнему abcd

Так почему верхний ответ в другом вопросе изменил строку на "bacd"? Я что-то упускаю из-за петель? Какой из них, i или mid равен 1, или в их ответе есть ошибка?

Заранее спасибо.

Answer 1

1. Введите первый вызов функции (mid = 0, end = 3).

   1. Введите итерацию первого цикла (i = 0 = mid)

   2. Поменяйте str[0] на себя.

   3. Введите второй вызов функции (mid = 1, end = 3).

      1. Введите итерацию первого цикла: i = mid = 1.

      2. Поменять str[1] на себя.

      3. Введите третий вызов функции (mid = 2, end = 3).

         1. Введите итерацию первого цикла: i = mid = 2.

         2. Обмен str[2] с собой.

         3. Введите четвертый функциональный вызов (mid = end = 3).

            4. Строка до сих пор не изменилась, поэтому мы печатаем abcd.

         4. Поменять str[2] на себя.

         5. Введите итерацию второго цикла: i = 3

         6. Обмен str[2] с str[3] (abcd -> abdc).

         7. Введите другой вызов функции (mid = end = 3).

            4. Мы печатаем abdc.

         8. Поменяйте местами str[2] с str[3] (назад к abcd).

         9. Цикл готов.

      4. Обмен str[1] с собой

      5. Введите итерацию второго цикла: i = 2

      6. И так далее ...

---

Программа воспроизведена здесь для удобства чтения:

void string_permutation(string str, int mid, int end)
{
    if (mid == end) 
        cout << str << endl;
    else 
    {
        for (int i = mid; i <= end; i++) 
        {
            swap(str[mid], str[i]);
            string_permutation(str, mid + 1, end);
            swap(str[mid], str[i]);
        }
    }
}

---

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

---

Легко видеть, что эта программа вызывает string_permutation N! (факториальное) время (каждый вызов приводит к end-mid большему количеству вызовов, при этом mid увеличивается на единицу). Также легко увидеть, что каждая пара swap восстанавливает строку до того, как она была при входе в функцию. В любой данный mid алгоритм помещает каждый из символов от mid до end в положение mid и рекурсивно. По индукции (базовый случай mid = end) мы видим, что все перестановки учитываются таким образом.

Однако алгоритм неправильно обрабатывает повторяющиеся символы. Я рекомендую std::next_permutation.