Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > String Permutation function in C

Reply
Thread Tools

String Permutation function in C

 
 
Sriram Rajagopalan
Guest
Posts: n/a
 
      10-29-2003
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


 
Reply With Quote
 
 
 
 
carl mcguire
Guest
Posts: n/a
 
      10-29-2003


Sriram Rajagopalan wrote:
> 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
>

Prbly nt, u cld 4sk in cmp.prgrmmr tho, sum1 thr mght hlp u wth an algrthm.
If u hv a prblm wth the actl C cde u rite, cme bk and sum1 shld b able 2
hlp u.
If u r hving prblems undrstnding ths msg, nxt tme sp3ak fr1kk1ng English
and not d00dsp3ak.

 
Reply With Quote
 
 
 
 
Sriram Rajagopalan
Guest
Posts: n/a
 
      10-29-2003
g??d w?y ?? -ncrypt??n... keep it up!!!

"carl mcguire" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
>
>
> Sriram Rajagopalan wrote:
> > 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
> >

> Prbly nt, u cld 4sk in cmp.prgrmmr tho, sum1 thr mght hlp u wth an

algrthm.
> If u hv a prblm wth the actl C cde u rite, cme bk and sum1 shld b able 2
> hlp u.
> If u r hving prblems undrstnding ths msg, nxt tme sp3ak fr1kk1ng English
> and not d00dsp3ak.
>



 
Reply With Quote
 
Tristan Miller
Guest
Posts: n/a
 
      10-29-2003
Greetings.

In article <VYOnb.7976$(E-Mail Removed)>, Sriram Rajagopalan wrote:
> g??d w?y ?? -ncrypt??n... keep it up!!!


Your news client is broken. Before posting a message with high-bit
characters, please find one that can set the character set properly.

--
_
_V.-o Tristan Miller [en,(fr,de,ia)] >< Space is limited
/ |`-' -=-=-=-=-=-=-=-=-=-=-=-=-=-=-= <> In a haiku, so it's hard
(7_\\ http://www.nothingisreal.com/ >< To finish what you
 
Reply With Quote
 
Joona I Palaste
Guest
Posts: n/a
 
      10-29-2003
carl mcguire <(E-Mail Removed)> scribbled the following:
> Sriram Rajagopalan wrote:
>> 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:
>>

> Prbly nt, u cld 4sk in cmp.prgrmmr tho, sum1 thr mght hlp u wth an algrthm.
> If u hv a prblm wth the actl C cde u rite, cme bk and sum1 shld b able 2
> hlp u.
> If u r hving prblems undrstnding ths msg, nxt tme sp3ak fr1kk1ng English
> and not d00dsp3ak.


U da man, carl! We should probably have some kind of rule: "Questions
written in h4x0r d00dsp33k rather than normal English will not be
answered".

--
/-- Joona Palaste ((E-Mail Removed)) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"Shh! The maestro is decomposing!"
- Gary Larson
 
Reply With Quote
 
Richard Heathfield
Guest
Posts: n/a
 
      10-29-2003
Sriram Rajagopalan wrote:

> Hi,
> Can ne 1 give me the logic of permuting a string in C language.


Since ne 1 doesn't seem to be responding, I'll have a go.

> What I meant is that suppose if u


"you", not "u"

> have a string like
>
> "man"
> the output should b:
>
> man
> mna
> amn
> anm
> nam
> nma


In other words, you take each letter of the string in turn, and set it as
the first letter in the output, and then you recurse into the rest of the
string.

Take a look at http://users.powernet.co.uk/eton/c/ttt.c which demonstrates
the technique (using a noughts-and-crosses board rather than a string, but
the principle is the same).

--
Richard Heathfield : http://www.velocityreviews.com/forums/(E-Mail Removed)
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton
 
Reply With Quote
 
Shankar Swamy
Guest
Posts: n/a
 
      10-30-2003
"Sriram Rajagopalan" <(E-Mail Removed)> wrote in message news:<pQNnb.7971$(E-Mail Removed)>...
> 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[i] = 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[i] ) continue ;
pcOut[iLevel] = pcIn[i] ;
pcMark[i] = 1 ;
DoPermute( pcIn, pcOut, pcMark, iLen, iLevel+1 ) ;
pcMark[i] = 0 ;
}

return ;

}

-------------------------------------------------------------------------
- shankar
-------------------------------------------------------------------------
shankarATcsDoTindinaDoTedu
 
Reply With Quote
 
nrk
Guest
Posts: n/a
 
      10-30-2003
Sriram Rajagopalan wrote:

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

Not the most efficient way of doing it, but hey, who's complaining about
killing the cat by suffocating it in cream

#include <stdio.h>

void permute(char *str, const int strt, const int len) {
int i = strt;
int j;
char temp;

for ( i = strt; i < len-1; ++i ) {
for ( j = i+1; j < len; ++j ) {
temp = str[i], str[i] = str[j], str[j] = temp;
permute(str, i+1, len);
temp = str[i], str[i] = str[j], str[j] = temp;
}
}
printf("%s\n", str);
}

int main(void) {
char str[] = "1234";

permute(str, 0, sizeof str - 1);

return 0;
}

HTH,
-nrk.

> Regards,
> Sriram Rajagopalan


 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[help] String permutation with input fadliwdt C Programming 0 11-17-2006 11:19 PM
[help] String permutation with input fadliwdt C Programming 0 11-17-2006 11:00 PM
Permutation Generator Talin Python 10 08-15-2005 03:27 PM
algorithm for finding permutation of characters m sergei C++ 4 06-29-2004 08:04 AM
Permutation lists?? Really Need Help Roger B. C++ 13 09-26-2003 02:21 AM



Advertisments