String Permutation function in C

Discussion in 'C Programming' started by Sriram Rajagopalan, Oct 29, 2003.

  1. 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
    Sriram Rajagopalan, Oct 29, 2003
    #1
    1. Advertising

  2. Sriram Rajagopalan

    carl mcguire Guest

    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.
    carl mcguire, Oct 29, 2003
    #2
    1. Advertising

  3. g??d w?y ?? ¶§-ncrypt??n... keep it up!!!

    "carl mcguire" <> wrote in message
    news:...
    >
    >
    > 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.
    >
    Sriram Rajagopalan, Oct 29, 2003
    #3
  4. Greetings.

    In article <VYOnb.7976$>, 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
    Tristan Miller, Oct 29, 2003
    #4
  5. carl mcguire <> 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 () ------------- Finland --------\
    \-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
    "Shh! The maestro is decomposing!"
    - Gary Larson
    Joona I Palaste, Oct 29, 2003
    #5
  6. 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 :
    "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
    Richard Heathfield, Oct 29, 2003
    #6
  7. "Sriram Rajagopalan" <> wrote in message news:<pQNnb.7971$>...
    > 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 ;

    }

    -------------------------------------------------------------------------
    - shankar
    -------------------------------------------------------------------------
    shankarATcsDoTindinaDoTedu
    Shankar Swamy, Oct 30, 2003
    #7
  8. Sriram Rajagopalan

    nrk Guest

    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, str = str[j], str[j] = temp;
    permute(str, i+1, len);
    temp = str, str = 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
    nrk, Oct 30, 2003
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Roger B.
    Replies:
    13
    Views:
    593
    D.F.S.
    Sep 26, 2003
  2. m sergei
    Replies:
    4
    Views:
    11,092
    Philip Parker
    Jun 29, 2004
  3. Talin

    Permutation Generator

    Talin, Aug 12, 2005, in forum: Python
    Replies:
    10
    Views:
    15,007
    Gerard Flanagan
    Aug 15, 2005
  4. fadliwdt

    [help] String permutation with input

    fadliwdt, Nov 17, 2006, in forum: C Programming
    Replies:
    0
    Views:
    411
    fadliwdt
    Nov 17, 2006
  5. fadliwdt

    [help] String permutation with input

    fadliwdt, Nov 17, 2006, in forum: C Programming
    Replies:
    0
    Views:
    499
    fadliwdt
    Nov 17, 2006
Loading...

Share This Page