Understanding Recursion to generate permutations

Question

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

Answer 1

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:

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

Answer 2

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".

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.

Answer 3

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

Answer 4

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

Answer 5

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.

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".

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.

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.

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

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!.

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

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

Answer 6

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.

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.

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

First iteration: choose a char from {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.

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.

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.

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

The swap statement in your code does this set construction. It splits the string into two sets free set to choose from used set that are already used. All chars on left side of i+1 is used set and 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 c and construct {a,c}, {b,d} using swapping.

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.