Zrozumienie rekurencji w celu generowania permutacji

Wybiera każdy znak ze wszystkich możliwych znaków:

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

Aby efektywnie wykorzystać rekurencję w projektowaniu, rozwiązujesz problem zakładając, że już go rozwiązałeś . Mentalną trampoliną dla obecnego problemu jest "gdybym mógł obliczyć permutacje znaków n-1, to mógłbym obliczyć permutacje znaków N, wybierając każdy z nich po kolei i dołączając permutacje pozostałych znaków n-1, Co udaję, że już wiem, jak to zrobić".

Wtedy potrzebujesz sposobu na to, co nazywa się" bottoming out " the rekurencja. Ponieważ każdy nowy sub-problem jest mniejszy niż ostatni, być może w końcu dojdziesz do sub-problem, który naprawdę wiesz, jak rozwiązać.

W tym przypadku, znasz już wszystkie permutacje jednego znaku - to tylko znak. Więc wiesz, jak rozwiązać to dla n=1 i dla każdej liczby, która jest o jeden więcej niż liczba, którą możesz rozwiązać i gotowe. Jest to bardzo ściśle związane z czymś, co nazywa się indukcją matematyczną.

Chociaż jest to trochę stare pytanie i już odpowiedział myślałem o dodaniu moich wejść, aby pomóc nowym odwiedzającym. Planuje również wyjaśnienie czasu pracy bez skupiania się na rekurencyjnym pojednaniu.

Sample napisałem w C# , ale łatwe do zrozumienia dla większości programistów.

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

Kroki: Dla np. gdy przekazujemy dane wejściowe jako "ABC".

1. metoda permutacji wywołana z Main po raz pierwszy. Więc wywołanie z indeksem 0 i to jest pierwsze sprawdzam.
2. w części else w pętli for powtarzamy od 0 do 2 wykonując 1 wywołanie za każdym razem.
3. pod każdą pętlą wywołujemy rekurencyjnie lpcnt + 1. 4.1 gdy indeks wynosi 1, to 2 wywołania rekurencyjne. 4.2 gdy indeks wynosi 2, to 1 wywołania rekurencyjne.

Tak więc z punktu 2 do 4.2 w sumie połączeń jest 5 dla każdej pętli, a w sumie to 15 połączeń + wejście główne = 16. Za każdym razem loopCnt wynosi 3, wtedy jeśli warunek zostanie wykonany.

Na wykresie widzimy liczbę pętli, która staje się 3 łącznie 6 razy tj. wartość czynnikowa 3 tj. Długość wejściowa "ABC".

If polecenie 's for loop powtarza' N 'razy, aby wyświetlić znaki z przykładu" ABC " tj. 3. Łącznie 6 razy (czasy czynnikowe) wchodzimy w if, aby wyświetlić permutacje. Więc całkowity czas pracy = n X n!.

Podałem statyczne zmienne CallCnt i tabelę, aby szczegółowo zrozumieć wykonanie każdej linii.

Eksperci, zapraszam do edycji mojej odpowiedzi lub komentarza, jeśli któraś z moich danych nie jest jasna lub niepoprawne, cieszę się, że je poprawiłem.

Pobierz przykładowy kod i inne próbki stąd

Ten kod i odniesienie mogą pomóc ci go zrozumieć.

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

Odniesienie: Geeksforgeeks.org

Chciałbym dodać tutaj Moje 2 centy z implementacją JavaScript. Możesz przeglądać dzienniki konsoli, a także usuwać mylące linie 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("");
}

Wyjście:

Obraz drzewa pochodzi zhttp://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

Również jako strona dla programów rekurencyjnych: