0

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;
}
2
Contributors
1
Reply
22
Views
3 Years
Discussion Span
Last Post by David W
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;
}

Edited by David W: fixed

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.