C++ 了解递归以生成排列

Understanding Recursion to generate permutations

提问by Nemo

I find recursion, apart from very straight forward ones like factorial, very difficult to understand. The following snippet prints all permutations of a string. Can anyone help me understand it. What is the way to go about to understand recursion properly.

我发现递归，除了像阶乘这样非常直接的递归，很难理解。以下代码段打印字符串的所有排列。任何人都可以帮助我理解它。正确理解递归的方法是什么。

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

回答by user786653

PaulR has the right suggestion. You have to run through the code by "hand" (using whatever tools you want - debuggers, paper, logging function calls and variables at certain points) until you understand it. For an explanation of the code I'll refer you to quasiverse's excellent answer.

PaulR 有正确的建议。您必须通过“手工”（使用您想要的任何工具——调试器、文件、记录函数调用和某些点的变量）来运行代码，直到你理解它。有关代码的解释，我将向您推荐 quasiverse 的出色答案。

Perhaps this visualization of the call graph with a slightly smaller string makes it more obvious how it works:

也许这种使用稍微小一点的字符串可视化调用图使它的工作原理更加明显：

The graph was made with graphviz.

该图是用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)"];
}

回答by flight

It chooses each character from all the possible characters left:

它从剩余的所有可能字符中选择每个字符：

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

回答by phunctor

To use recursion effectively in design, you solve the problem by assuming you've already solved it. The mental springboard for the current problem is "if I could calculate the permutations of n-1 characters, then I could calculate the permutations of n characters by choosing each one in turn and appending the permutations of the remaining n-1 characters, which I'm pretending I already know how to do".

为了在设计中有效地使用递归，您可以通过假设您已经解决了问题来解决问题。当前问题的心理跳板是“如果我可以计算 n-1 个字符的排列，那么我可以通过依次选择每个字符并附加剩余的 n-1 个字符的排列来计算 n 个字符的排列，我'假装我已经知道该怎么做'。

Then you need a way to do what's called "bottoming out" the recursion. Since each new sub-problem is smaller than the last, perhaps you'll eventually get to a sub-sub-problem that you REALLY know how to solve.

然后，您需要一种方法来执行所谓的“触底”递归。由于每个新的子问题都比上一个小，也许您最终会遇到一个您真正知道如何解决的子子问题。

In this case, you already know all the permutations of ONE character - it's just the character. So you know how to solve it for n=1 and for every number that's one more than a number you can solve it for, and you're done. This is very closely related to something called mathematical induction.

在这种情况下，您已经知道 ONE 字符的所有排列 - 这只是字符。所以你知道如何解决 n=1 和每个比你能解决的数字大 1 的数字，你就完成了。这与所谓的数学归纳法密切相关。

回答by Sazzad Hissain Khan

This code and reference might help you to understand it.

此代码和参考可能会帮助您理解它。

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

Reference: Geeksforgeeks.org

参考：Geeksforgeeks.org

回答by Sai

Though it is little old question and already answered thought of adding my inputs to help new visitors. Also planning to explain the running time without focusing on Recursive Reconciliation.

尽管这是个小问题，并且已经回答了添加我的输入以帮助新访问者的想法。还计划在不关注递归协调的情况下解释运行时间。

I have written the sample in C# but easy to understand for most of the programmers.

我已经用 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);       
}

Steps:For e.g. when we pass input as "ABC".

步骤：例如，当我们将输入作为“ABC”传递时。

1. Permutations method called from Main for first time. So calling with Index 0 and that is first call.
2. In the else part in for loop we are repeating from 0 to 2 making 1 call each time.
3. Under each loop we are recursively calling with LpCnt + 1. 4.1 When index is 1 then 2 recursive calls. 4.2 When index is 2 then 1 recursive calls.

1. 第一次从 Main 调用的排列方法。所以用索引 0 调用，这是第一次调用。
2. 在 for 循环的 else 部分，我们从 0 到 2 重复，每次进行 1 次调用。
3. 在每个循环下，我们使用 LpCnt + 1 递归调用。 4.1 当索引为 1 时，将进行 2 次递归调用。4.2 当索引为 2 时，递归调用 1 次。

So from point 2 to 4.2 total calls are 5 for each loop and total is 15 calls + main entry call = 16. Each time loopCnt is 3 then if condition gets executed.

因此，从点 2 到 4.2，每个循环的总调用次数为 5，总调用次数为 15 次 + 主入口调用 = 16。每次 loopCnt 为 3 时，如果条件被执行。

From the diagram we can see loop count becoming 3 total 6 times i.e. Factorial value of 3 i.e. Input "ABC" length.

从图中我们可以看到循环计数变为 3 总共 6 次，即因子值为 3，即输入“ABC”长度。

If statement's for loop repeats 'n' times to display chars from the example "ABC" i.e. 3. Total 6 times (Factorial times) we enter into if to display the permutations. So the total running time = n X n!.

If 语句的 for 循环重复“n”次以显示示例“ABC”中的字符，即 3。总共 6 次（因子时间）我们进入 if 以显示排列。所以总运行时间 = n X n!。

I have given some static CallCnt variables and the table to understand each line execution in detail.

我已经给出了一些静态的 CallCnt 变量和表格来详细了解每一行的执行情况。

Experts, feel free to edit my answer or comment if any of my details are not clear or incorrect, I am happy correct them.

专家，如果我的任何细节不清楚或不正确，请随时编辑我的答案或评论，我很乐意纠正它们。

Download the sample code and other samples from here

从这里下载示例代码和其他示例

回答by Sureshkumar T

Think about the recursion as simply a number of levels. At each level, you are running a piece of code, here you are running a for loop n-i times at each level. this window gets decreasing at each level. n-i times, n-(i+1) times, n-(i+2) times,..2,1,0 times.

将递归视为简单的多个级别。在每个级别，您都在运行一段代码，在这里您在每个级别运行 for 循环 ni 次。这个窗口在每个级别都会减少。ni 次，n-(i+1) 次，n-(i+2) 次，..2,1,0 次。

With respect to string manipulation and permutation, think of the string as simply a 'set' of chars. "abcd" as {'a', 'b', 'c', 'd'}. Permutation is rearranging these 4 items in all possible ways. Or as choosing 4 items out of these 4 items in different ways. In permutations the order does matter. abcd is different from acbd. we have to generate both.

关于字符串操作和排列，将字符串视为简单的字符“集合”。"abcd" 为 {'a', 'b', 'c', 'd'}。排列是以所有可能的方式重新排列这 4 个项目。或者以不同的方式从这 4 个项目中选择 4 个项目。在排列中，顺序确实很重要。abcd 与 abd 不同。我们必须同时生成两者。

The recursive code provided by you exactly does that. In my string above "abcd", your recursive code runs 4 iterations (levels). In the first iteration you have 4 elements to choose from. second iteration, you have 3 elements to choose from, third 2 elements, and so on. so your code runs 4! calculations. This is explained below

您提供的递归代码正是这样做的。在“abcd”上方的字符串中，您的递归代码运行 4 次迭代（级别）。在第一次迭代中，您有 4 个元素可供选择。第二次迭代，您有 3 个元素可供选择，第三个 2 个元素，依此类推。所以你的代码运行 4！计算。这在下面解释

First iteration: choose a char from {a,b,c,d}

First iteration: 从 {a,b,c,d} 中选择一个字符

Second Iteration: choose a char from subtracted set {{a,b,c,d} - {x}} where x is the char chosen from first iteration. i.e. if 'a' has been choose in first iteration, this iteration has {b,c,d} to choose from.

Second Iteration：从减集 {{a,b,c,d} - {x}} 中选择一个字符，其中 x 是从第一次迭代中选择的字符。即如果在第一次迭代中选择了“a”，则这次迭代有 {b,c,d} 可供选择。

Third Iteration: choose a char from subtracted set {{a,b,c,d} - {x,y}} where x and y are chosen chars from previous iterations. i.e. if 'a' is chosen at first iteration, and 'c' is chosen from 2nd, we have {b,d} to play with here.

Third Iteration：从减去集合 {{a,b,c,d} - {x,y}} 中选择一个字符，其中 x 和 y 是从以前的迭代中选择的字符。即，如果在第一次迭代时选择了 'a'，而从第二次中选择了 'c'，那么我们有 {b,d} 可以在这里玩。

This repeats until we choose 4 chars overall. Once we choose 4 possible char, we print the chars. Then backtrack and choose a different char from the possible set. i.e. when backtrack to Third iteration, we choose next from possible set {b,d}. This way we are generating all possible permutations of the given string.

如此重复，直到我们总共选择了 4 个字符。一旦我们选择了 4 个可能的字符，我们就打印字符。然后回溯并从可能的集合中选择一个不同的字符。即当回溯到第三次迭代时，我们从可能的集合 { b,d} 中选择下一个。通过这种方式，我们生成了给定字符串的所有可能排列。

We are doing this set manipulations so that we are not selecting the same chars twice. i.e. abcc, abbc, abbd,bbbb are invalid.

我们正在执行此设置操作，以便我们不会两次选择相同的字符。即 abcc、abbc、abbd、bbbb 无效。

The swap statement in your code does this set construction. It splits the string into two sets free setto choose from used setthat are already used. All chars on left side of i+1is used setand right are free set. In first iteration, you are choosing among {a,b,c,d} and then passing {a}:{b,c,d} to next iteration. The next iteration chooses one of {b,c,d} and passes {a,b}:{c,d} to next iteration, and so on. When the control backtracks back to this iteration, you will then choose cand construct {a,c}, {b,d} using swapping.

代码中的 swap 语句执行此集合构造。它将字符串分成两组free set以从used set已使用的组中进行选择。i+1isused set和右边的所有字符都是free set。在第一次迭代中，您在 {a,b,c,d} 中进行选择，然后将 {a}:{b,c,d} 传递给下一次迭代。下一次迭代选择 {b,c,d} 之一并将 {a,b}:{c,d} 传递给下一次迭代，依此类推。当控制回溯到此迭代时，您将c使用交换选择和构造 {a,c}, {b,d}。

That's the concept. Otherwise, the recursion is simple here running n deep and each level running a loop for n, n-1, n-2, n-3...2,1 times.

这就是概念。否则，递归在这里很简单，运行 n 深，每个级别运行 n、n-1、n-2、n-3...2,1 次循环。