Понимание рекурсии для генерации перестановок

Question

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

void permute(char a[], int i, int n)
{
   int j;
   if (i == n)
     cout << a << endl;
   else
   {
       for (j = i; j <= n; j++)
       {
          swap(a[i], a[j]);          
          permute(a, i+1, n);
          swap(a[i], a[j]);
       }
   }
} 

int main()
{
   char a[] = "ABCD";
   permute(a, 0, 3);
   getchar();
   return 0;
}

Answer 1

PaulR имеет правильное предложение. Вы должны пробежаться по коду «вручную» (используя любые инструменты, которые вам нужны - отладчики, бумагу, запись вызовов функций и переменных в определенных точках), пока не поймете это. Для объяснения кода я отошлю вас к отличному ответу quasiverse.

Возможно, эта визуализация графа вызовов с немного меньшей строкой делает его более очевидным:

График был сделан с помощью graphviz .

// x.dot
// dot x.dot -Tpng -o x.png
digraph x {
rankdir=LR
size="16,10"

node [label="permute(\"ABC\", 0, 2)"] n0;
 node [label="permute(\"ABC\", 1, 2)"] n1;
  node [label="permute(\"ABC\", 2, 2)"] n2;
  node [label="permute(\"ACB\", 2, 2)"] n3;
 node [label="permute(\"BAC\", 1, 2)"] n4;
  node [label="permute(\"BAC\", 2, 2)"] n5;
  node [label="permute(\"BCA\", 2, 2)"] n6;
 node [label="permute(\"CBA\", 1, 2)"] n7;
  node [label="permute(\"CBA\", 2, 2)"] n8;
  node [label="permute(\"CAB\", 2, 2)"] n9;

n0 -> n1 [label="swap(0, 0)"];
n0 -> n4 [label="swap(0, 1)"];
n0 -> n7 [label="swap(0, 2)"];

n1 -> n2 [label="swap(1, 1)"];
n1 -> n3 [label="swap(1, 2)"];

n4 -> n5 [label="swap(1, 1)"];
n4 -> n6 [label="swap(1, 2)"];

n7 -> n8 [label="swap(1, 1)"];
n7 -> n9 [label="swap(1, 2)"];
}

Answer 2

Выбирает каждый символ из всех возможных оставшихся символов:

void permute(char a[], int i, int n)
{
    int j;
    if (i == n)                  // If we've chosen all the characters then:
       cout << a << endl;        // we're done, so output it
    else
    {
        for (j = i; j <= n; j++) // Otherwise, we've chosen characters a[0] to a[j-1]
        {                        // so let's try all possible characters for a[j]
            swap(a[i], a[j]);    // Choose which one out of a[j] to a[n] you will choose
            permute(a, i+1, n);  // Choose the remaining letters
            swap(a[i], a[j]);    // Undo the previous swap so we can choose the next possibility for a[j]
        }
    }
} 

Answer 3

Чтобы эффективно использовать рекурсию в дизайне, вы решаете проблему, предполагая, что вы уже решили ее . Ментальный трамплин для текущей проблемы: «Если бы я мог рассчитать перестановки из n-1 символов, то я мог бы рассчитать перестановки из n символов, выбрав каждый из них по очереди и добавив перестановки из оставшихся n-1 символов, которые я притворяюсь, я уже знаю, как это сделать ".

Тогда вам нужен способ сделать то, что называется "дна" рекурсии. Поскольку каждая новая подзадача меньше, чем предыдущая, возможно, в конечном итоге вы попадете на подзадачу, которую ДЕЙСТВИТЕЛЬНО знаете, как ее решить.

В этом случае вы уже знаете все перестановки ОДНОГО персонажа - это просто персонаж. Итак, вы знаете, как решить это для n = 1, и для каждого числа, которое на единицу больше, чем число, для которого вы можете решить это, и все готово. Это очень тесно связано с тем, что называется математической индукцией.

Answer 4

Этот код и ссылка могут помочь вам понять его.

// C program to print all permutations with duplicates allowed
#include <stdio.h>
#include <string.h>

/* Function to swap values at two pointers */
void swap(char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

/* Function to print permutations of string
   This function takes three parameters:
   1. String
   2. Starting index of the string
   3. Ending index of the string. */
void permute(char *a, int l, int r)
{
   int i;
   if (l == r)
     printf("%s\n", a);
   else
   {
       for (i = l; i <= r; i++)
       {
          swap((a+l), (a+i));
          permute(a, l+1, r);
          swap((a+l), (a+i)); //backtrack
       }
   }
}

/* Driver program to test above functions */
int main()
{
    char str[] = "ABC";
    int n = strlen(str);
    permute(str, 0, n-1);
    return 0;
}

Ссылка: Geeksforgeeks.org

Answer 5

Хотя это небольшой старый вопрос, и он уже ответил на мысль о том, чтобы добавить свои материалы, чтобы помочь новым посетителям. Также планируется объяснить время выполнения, не сосредотачиваясь на рекурсивной сверке.

Я написал пример на C #, но его легко понять большинству программистов.

static int noOfFunctionCalls = 0;
static int noOfCharDisplayCalls = 0;
static int noOfBaseCaseCalls = 0;
static int noOfRecursiveCaseCalls = 0; 
static int noOfSwapCalls = 0;
static int noOfForLoopCalls = 0;

static string Permute(char[] elementsList, int currentIndex)
{
    ++noOfFunctionCalls;

    if (currentIndex == elementsList.Length)
    {
        ++noOfBaseCaseCalls;        
        foreach (char element in elementsList)
        {
            ++noOfCharDisplayCalls;

            strBldr.Append(" " + element);
        }
        strBldr.AppendLine("");
    }
    else
    {
        ++noOfRecursiveCaseCalls;

        for (int lpIndex = currentIndex; lpIndex < elementsList.Length; lpIndex++)
        {
            ++noOfForLoopCalls;

            if (lpIndex != currentIndex)
            {
                ++noOfSwapCalls;
                Swap(ref elementsList[currentIndex], ref elementsList[lpIndex]);
            }

            Permute(elementsList, (currentIndex + 1));

            if (lpIndex != currentIndex)
            {
                Swap(ref elementsList[currentIndex], ref elementsList[lpIndex]);
            }
        }
    }
    return strBldr.ToString();
}

static void Swap(ref char Char1, ref char Char2)
{
    char tempElement = Char1;
    Char1 = Char2;
    Char2 = tempElement;
}      

public static void StringPermutationsTest()
{
    strBldr = new StringBuilder();
    Debug.Flush();

    noOfFunctionCalls = 0;
    noOfCharDisplayCalls = 0;
    noOfBaseCaseCalls = 0;
    noOfRecursiveCaseCalls = 0;
    noOfSwapCalls = 0;
    noOfForLoopCalls = 0;

    //string resultString = Permute("A".ToCharArray(), 0);
    //string resultString = Permute("AB".ToCharArray(), 0);
    string resultString = Permute("ABC".ToCharArray(), 0);
    //string resultString = Permute("ABCD".ToCharArray(), 0);
    //string resultString = Permute("ABCDE".ToCharArray(), 0);

    resultString += "\nNo of Function Calls : " + noOfFunctionCalls;
    resultString += "\nNo of Base Case Calls : " + noOfBaseCaseCalls;
    resultString += "\nNo of General Case Calls : " + noOfRecursiveCaseCalls;
    resultString += "\nNo of For Loop Calls : " + noOfForLoopCalls;
    resultString += "\nNo of Char Display Calls : " + noOfCharDisplayCalls;
    resultString += "\nNo of Swap Calls : " + noOfSwapCalls;

    Debug.WriteLine(resultString);
    MessageBox.Show(resultString);       
}

Шаги: Например, когда мы передаем ввод как "ABC".

1. Метод перестановок, вызываемый из Main впервые. Итак, вызов с индексом 0 и это первый вызов.
2. В остальной части цикла for мы повторяем от 0 до 2, каждый раз делая 1 вызов.
3. В каждом цикле мы рекурсивно вызываем с помощью LpCnt + 1. 4.1 Если индекс равен 1, то 2 рекурсивных вызова. 4.2 Если индекс равен 2, то 1 рекурсивные вызовы.

Таким образом, от пункта 2 до 4.2 общее количество вызовов составляет 5 для каждого цикла, а общее количество вызовов составляет 15 + главный вход = 16. Каждый раз, когда loopCnt равен 3, тогда, если условие выполнено.

На диаграмме видно, что число циклов становится в 3 раза больше 6, т.е. факториальное значение 3, т. Е. Длина ввода "ABC".

Если оператор for цикл повторяется n раз для отображения символов из примера "ABC", то есть 3. Всего 6 раз (факториальное время) мы вводим, если отображать перестановки. Таким образом, общее время работы = n X n!.

Я дал несколько статических переменных CallCnt и таблицу для подробного понимания выполнения каждой строки.

Эксперты, не стесняйтесь редактировать мой ответ или комментарий, если какие-либо мои данные не ясны или неверны, я рад их исправить.

Загрузите образец кода и другие образцы здесь

Answer 6

Думайте о рекурсии как о просто ряде уровней. На каждом уровне вы выполняете фрагмент кода, здесь вы выполняете цикл for n-i раз на каждом уровне. это окно уменьшается на каждом уровне. n-i раз, n- (i + 1) раз, n- (i + 2) раза, .. 2,1,0 раза.

Что касается манипулирования и перестановки строк, думайте о строке как о «наборе» символов. "abcd" как {'a', 'b', 'c', 'd'}. Перестановка переставляет эти 4 пункта всеми возможными способами. Или как выбрать 4 пункта из этих 4 пунктов разными способами. В перестановках порядок имеет значение. abcd отличается от acbd. мы должны генерировать оба.

Предоставленный вами рекурсивный код именно так и делает. В моей строке выше "abcd" ваш рекурсивный код выполняет 4 итерации (уровня). В первой итерации у вас есть 4 элемента на выбор. вторая итерация, у вас есть 3 элемента на выбор, третьи 2 элемента и так далее. так что ваш код работает 4! расчеты. Это объясняется ниже

First iteration: выберите символ из {a, b, c, d}

Second Iteration: выберите символ из вычтенного множества {{a, b, c, d} - {x}}, где x - символ, выбранный из первой итерации. то есть, если «a» было выбрано на первой итерации, эта итерация может выбирать из {b, c, d}.

Third Iteration: выберите символ из вычтенного множества {{a, b, c, d} - {x, y}}, где x и y - выбранные символы из предыдущих итераций. то есть, если на первой итерации выбрано «а», а на 2-й выбрано «с», то здесь нам нужно поиграть {b, d}.

Это повторяется, пока мы не выберем 4 символа в целом. Как только мы выбираем 4 возможных символа, мы печатаем символы. Затем вернитесь назад и выберите другого персонажа из возможного набора. т.е. когда мы возвращаемся к третьей итерации, мы выбираем следующий из возможных наборов {b, d}. Таким образом, мы генерируем все возможные перестановки данной строки.

Мы выполняем этот набор манипуляций, чтобы мы не выбирали одни и те же символы дважды. то есть abcc, abbc, abbd, bbbb недействительны.

Оператор swap в вашем коде выполняет эту конструкцию набора. Он разбивает строку на два набора free set на выбор used set, которые уже используются. Все символы слева i+1 равны used set, а справа free set. На первой итерации вы выбираете среди {a, b, c, d} и затем передаете {a}: {b, c, d} на следующую итерацию. Следующая итерация выбирает одну из {b, c, d} и передает {a, b}: {c, d} на следующую итерацию и так далее. Когда элемент управления вернется к этой итерации, вы выберете c и создадите {a, c}, {b, d}, используя обмен.

Это концепция. В противном случае, рекурсия здесь проста, она работает на глубину n, а каждый уровень запускает цикл n, n-1, n-2, n-3 ... 2,1 раза