Understanding Recursion to generate permutations

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.

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

The graph was made with 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)"];
}

Related Posts:

  1. how to implement quick sort algorithm in C++
  2. C++ convert from 1 char to string?
  3. Pause Console in C++ program
  4. What is the easiest way to initialize a std::vector with hardcoded elements?
  5. Vector of Vectors to create matrix
  6. std::string to char*
  7. How to generate a random number in C++?
  8. Why are #ifndef and #define used in C++ header files?
  9. c++ “Incomplete type not allowed” error accessing class reference information (Circular dependency with forward declaration)
  10. C++ Error: undefined reference to `main’
  11. 1.#QNAN error C++
  12. What is the array form of ‘delete’?
  13. Error: Expression must have integral or unscoped enum type
  14. Use new operator to initialise an array
  15. Remove secure warnings (_CRT_SECURE_NO_WARNINGS) from projects by default in Visual Studio
  16. Undefined Symbols for architecture x86_64: Compiling problems
  17. “No viable overloaded ‘=’ ” why?
  18. Check if a string contains a string in C++
  19. Efficient way to return a std::vector in c++
  20. “No viable overloaded ‘=’ ” why?
  21. Replace part of a string with another string
  22. What does “<<" and ">>” mean in C++ for cout/cin?
  23. C ++ error: a expected initializer before [function name]
  24. invalid new-expression of abstract class type
  25. std::string to char*
  26. Does the ‘mutable’ keyword have any purpose other than allowing the variable to be modified by a const function?
  27. SDL2.DLL missing
  28. Argument list for class template is missing
  29. Fastest way to check if a file exist using standard C++/C++11,14,17/C?
  30. Cleanest way to copy a constant size array in c++11
  31. Difference between using Makefile and CMake to compile the code
  32. Exception Error c0000005 in VC++
  33. push_back vs emplace_back
  34. Parsing a comma-delimited std::string
  35. Random number c++ in some range
  36. “g++” is not recognized as an internal or external command, MinGW
  37. Compiling a C++ program with gcc
  38. C++ BlackJack Stuck trying to program Ace
  39. Convert a String In C++ To Upper Case
  40. Is std::stoi actually safe to use?
  41. What’s the syntax for declaring an array of function pointers without using a separate typedef?
  42. What is the difference between const_iterator and non-const iterator in the C++ STL?
  43. Sorting Linked List C++ with pointers
  44. Get Unix timestamp with C++
  45. Class prototyping
  46. How to dynamically allocate an array of pointers in C++?
  47. How do I compile C++ to JavaScript in a browser?
  48. Is the sizeof(some pointer) always equal to four?
  49. How do you initialise a dynamic array in C++?
  50. What are the distinctions between the various symbols (*,&, etc) combined with parameters?
  51. Accessors and Mutators C++
  52. Error C1083: Cannot open include file: ‘stdafx.h’
  53. How do you handle a “cannot instantiate abstract class” error in C++?
  54. C++ Simple hangman game
  55. “The system cannot find the file specified” when running C++ program
  56. Remove First and Last Character C++
  57. C++ Convert string (or char*) to wstring (or wchar_t*)
  58. Program received signal SIGSEGV, Segmentation fault
  59. Integer to hex string in C++
  60. Comparison of C++ unit test frameworks
  61. What is the difference between .cc and .cpp file suffix?
  62. C++ error: object of abstract class type is not allowed: pure virtual function has no overrider
  63. Correct way to work with vector of arrays
  64. What’s the difference between nexti and stepi in gdb?
  65. How to get current time in milliseconds?
  66. Resizing dynamic array in c++
  67. C++ – Nested include – Avoiding ‘include nested too deeply error’
  68. Trying to use int in getline
  69. c++ error c2015: too many characters in constant
  70. Splitting a C++ std::string using tokens, e.g. “;”
  71. Py_Initialize fails – unable to load the file system codec
  72. C++ pass an array by reference
  73. error LNK2019: unresolved external symbol “” referenced in function
  74. Undefined reference to a static member
  75. How to sort with a lambda?
  76. stoi function gives error: std::invalid_argument at memory location 0x0035E8D8. c++
  77. Stack around the variable ‘ ‘ was corrupted
  78. Error in assignment of member in read-only object
  79. creating an array of structs in c++
  80. What’s the Use of ‘\r’ escape sequence?
  81. How do I use an enum value in a switch statement in C++?
  82. Why should I use a pointer rather than the object itself?
  83. Call of overloaded function is ambiguous
  84. ‘cout’ does not name a type
  85. C++ Cannot call constructor directly in small example
  86. C++ compiler error c4430 “c++ doesnt support default int”
  87. Using OpenMP with clang
  88. Using cin for char array
  89. invalid use of ‘this’ outside of a non-static member function error?
  90. Dev C++ compilation error, permission denied
  91. convert string to size_t
  92. Download c++ in existing visual studio 2017
  93. istream and ostream problem – C++
  94. List iterator not dereferencable?
  95. How do you convert CString and std::string std::wstring to each other?
  96. C++ Swapping Pointers
  97. C++ classes (public, private, and protected)
  98. Here is some error with my .h file which show [Error] unterminated #ifndef when I include my class template in it
  99. How to Read from a Text File, Character by Character in C++
  100. C++ error C2181: illegal else without matching if

Leave a Comment