了解递归以生成排列

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-1个字符的排列来计算n个字符的排列,我假装我已经知道该怎么做了".

然后你需要一种方法去做所谓的"触底反弹"递归.由于每个新的子问题都小于最后一个问题,或许你最终会遇到一个你真正知道如何解决的子问题.

在这种情况下,你已经知道了一个角色的所有排列 - 它只是角色.因此,您知道如何解决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