Start New Discussion within our Software Development Community

i have a c code for printing all permutation of string. I have a problem in understanding ,how recursion work in for loop and how backtracking is used in this code. Another question is that how stack work in recursion under for loop.
my code-->

# include <stdio.h>
void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

void permute(char *a, int i, int n) 
{
   int j; 
   if (i == n)
     printf("%s\n", a);
   else
   {
        for (j = i; j <= n; j++)
       {
          swap((a+i), (a+j));
          permute(a, i+1, n);
          swap((a+i), (a+j)); //backtrack
       }
   }
} 

int main()
{
   char a[] = "ABC";  
   permute(a, 0, 2);
   getchar();
   return 0;
}

This modified code example may help you to see what is being done as the program executes ...

/* permutationsOfString.c  */  /* 2014-02-25 */

/*
    I have an example, coded in C, for printing all permutation of string.

    I have a problem in understanding,
    how recursion works in a for loop
    and how backtracking is used in this code.

    Another question is that how stack work in recursion under for loop.

    code-->

*/

# include <stdio.h>

#define show 1

void swap( char* x, char* y )
{
    char tmp = *x;
    *x = *y;
    *y = tmp;
}

void permute( char* a, int i, int n )
{
    int j;
    static int count = 0;
    if( i == n )
    {
        printf( "%s, i=%d, count=%d\n", a, i, ++count );
#if show
        putchar( '\n' );
#endif
    }
    else
    {
        for( j = i; j <= n; ++j )
        {
#if show
            printf( "%s, i=%d, j=%d\n", a, i, j );
#endif
            swap( (a+i), (a+j) );
            permute( a, i+1, n );
            swap( (a+i), (a+j) ); /* backtrack */
        }
    }
}


int main()
{
    char a[] = "ABCD";
    permute( a, 0, 3 );

    printf( "Press 'Enter' to continue/exit ... " );
    getchar();
    return 0;
}
This article has been dead for over six months. Start a new discussion instead.