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

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

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;
}

Ответы

Ответ 1

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

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

График был сделан с 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)"];
}

Ответ 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 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]
        }
    }
}

Ответ 3

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

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

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

Ответ 4

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

Я написал образец на С#, но его легко понять для большинства программистов.

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" .

  • Метод перестановок, вызванный из Main для первого раза. Поэтому вызов с индексом 0 и первым вызовом.
  • В цикле else in for мы повторяем от 0 до 2, делая каждый раз каждый раз.
  • В каждом цикле мы рекурсивно вызываем LpCnt + 1. 4.1. Когда индекс равен 1, то 2 рекурсивных вызова. 4.2 Когда индекс равен 2, а затем 1 рекурсивный вызов.

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

Из диаграммы видно, что количество циклов становится 3 общим 6 раз, т.е. факториальное значение 3, т.е. вводит длину "ABC" .

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

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

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

enter image description hereenter image description here

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

Ответ 5

введите описание изображения здесь

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

// 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

Ответ 6

Я хотел бы добавить свои 2 цента здесь с реализацией JavaScript. Вы можете просматривать журналы консоли, а также удалять путаные строки console.log;

let str = "ABC";

permute(str, 0, str.length - 1, 0);

function permute(str, left, right, depth) {
  console.log(
    "called by depth:",
    depth,
    "str:",
    str,
    "left:",
    left,
    "right:",
    right
  );
  if (left === right) {
    console.log("PRINT:", str + "\n");
  } else {
    for (let i = left; i <= right; i++) {
      str = swap(str, left, i);
      console.log(
        "swap:",
        str,
        "depth:",
        depth,
        "left:",
        left,
        "inner counter:",
        i
      );
      console.log(
        "call permute",
        "str:",
        str,
        "depth:",
        depth + 1,
        "start left:",
        str[left + 1],
        "until right:",
        str[right]
      );
      permute(str, left + 1, right, depth + 1);
      str = swap(str, left, i);
      console.log(
        "backtrack swap",
        "depth:",
        depth,
        "str:",
        str,
        "left:",
        left,
        "right:",
        i
      );
    }
  }
}

function swap(str, left, right) {
  let charArr = str.split("");
  let leftTemp = charArr[left];
  charArr[left] = charArr[right];
  charArr[right] = leftTemp;
  return charArr.join("");
}

ВЫВОД:

enter image description here

Дерево изображение с http://www.geeksforgeeks.org/write-ac-program-to-print-all-permutations-of-a-given-string/

Также как сторона для рекурсивных программ:

enter image description here