了解recursion生成排列

我发现recursion，除了象阶乘这样非常简单的recursion之外，很难理解。 以下片段打印一个string的所有排列。 任何人都可以帮助我理解它。 什么是正确理解recursion的方法。

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有正确的build议。 你必须通过“手”（使用任何你想要的工具 – debugging器，纸，logging函数调用和某些点的variables）来运行代码，直到你理解它。 对于代码的解释，我会引用你的quasiverse的优秀答案。

也许这个带有更小string的调用图的可视化使得它更加明显：

该图是用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

它从所有可能的字符中select每个字符：

 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

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

那么你需要一种方法来做所谓的“触底”recursion。 由于每个新的子问题都比上一个小，所以最终你可能会遇到一个你真正知道如何解决的子问题。

在这种情况下，你已经知道一个angular色的所有排列 – 只是angular色。 所以你知道如何解决它n = 1和每个数字比一个数字多一个，你可以解决它，你就完成了。 这与math归纳法非常接近。

Answer 4

虽然这个问题不大，但已经回答了join我的意见，以帮助新的访问者。 还计划解释运行时间，而不用关注recursion调整。

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

步骤：例如，当我们通过input作为“ABC”。

1. 首次从Main调用的排列方法。 所以调用索引0，这是第一个电话。
2. 在for循环中的else部分，我们重复从0到2，每次调用1次。
3. 在每个循环下，我们用LpCnt + 1recursion调用。4.1当索引是1，然后是2个recursion调用。 4.2当索引是2，然后1recursion调用。

所以从第2点到第4.2点，每个循环总共有5个呼叫，总数为15个呼叫+主要呼入呼叫= 16。每次循环次数为3，则条件得到执行。

从图中我们可以看到循环计数变成总共6次，即3的阶乘值即input“ABC”长度。

如果语句for循环重复“n”次来显示例子“ABC”中的字符，也就是3.总共6次（阶乘次数）我们进入if是否显示排列。 所以总运行时间= n X n !.

我给了一些静态的CallCntvariables和表来详细了解每一行的执行情况。

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

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

Answer 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