Sriram Rajagopalan said:
Hi,
Can ne 1 give me the logic of permuting a string in C language.
What I meant is that suppose if u have a string like
"man"
the output should b:
man
mna
amn
anm
nam
nma
Regards,
Sriram Rajagopalan
You have to do a "mark and recurse" algorithm. That is, taking your
example, first create an array - pcOut[] - that is 3+1 characters
wide. Now place the first character in pcOut[0], and mark that
character. Do this part iteratively with each character in your input.
Once you have a character placed in the pcOut[0] position, you can
place any character but the pcOut[0] character at pcOut[1]. Do a
recursive call by properly passing the marked characters into the
call. That should solve the problem.
There might be other ways of doing it - I did not think hard enough.
I just whipped up what came to my mind when I saw this. This seems to
work though. If you find a better way or find bugs in this, let's
know.
Here is what seems to work - I vefied it on two strings.
PS: Commenting the code is left as an exercise for you, before turning
in the home work
------------------------------------------------------------------------------------
/* gcc -D__TESTING__ -o permutations permutations.c */
#include <stdlib.h>
#include<stdio.h>
void DoPermute( const char* const pcIn, char* const pcOut,
char* const pcMark, const int iLen, const int iLevel ) ;
void Permute( const char* const s ) ;
#if __TESTING__
int main(int argc, char* argv[]) {
char caIn[] = "man" ;
printf("Permutations of %s : \n", caIn) ;
Permute( caIn ) ;
char caIn2[] = "ABCD" ;
printf("\n\nPermutations of %s : \n", caIn2) ;
Permute( caIn2 ) ;
return EXIT_SUCCESS ;
} /* int main(...) */
#endif
void Permute( const char* const s ){
int iLen = strlen(s), i ;
char* const pcMark = (char*)malloc(iLen) ;
char* const pcOut = (char*)malloc(iLen+1) ;
if( !pcMark || !pcOut ){
printf( "Malloc for pcMark or pcOut (or both) failed; bailing
out!\n" ) ;
return ;
}
pcOut[iLen] = 0 ;
for(i=0; i<iLen; i++) pcMark
= 0
;
DoPermute( s, pcOut, pcMark, iLen, 0 ) ;
free( pcMark ) ;
free( pcOut ) ;
}
void DoPermute( const char* const pcIn, char* const pcOut,
char* const pcMark, const int iLen, const int iLevel ) {
int i = 0 ; static int iTot = 1 ;
/* If DoPermute(...) from different instances, reset the counter at
the beginning of each instance*/
if(!iLevel) iTot = 1 ;
if( iLen == iLevel ){
printf( "%*d %s\n", 3, iTot++, pcOut ) ;
return ;
}
for(i=0; i < iLen; i++){
if( pcMark ) continue ;
pcOut[iLevel] = pcIn ;
pcMark = 1 ;
DoPermute( pcIn, pcOut, pcMark, iLen, iLevel+1 ) ;
pcMark = 0 ;
}
return ;
}