print all permutations of string

Discussion in 'C++' started by anurag, Jul 20, 2006.

  1. anurag

    anurag Guest

    hey can anyone help me in writing a code in c (function) that prints
    all permutations of a string.please help
     
    anurag, Jul 20, 2006
    #1
    1. Advertising

  2. anurag wrote:
    > hey can anyone help me in writing a code in c (function) that prints
    > all permutations of a string.please help


    Please, for C questions do not cross-post to comp.lang.c++. Thanks!

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Jul 20, 2006
    #2
    1. Advertising

  3. anurag

    Flash Gordon Guest

    anurag wrote:
    > hey can anyone help me in writing a code in c (function) that prints
    > all permutations of a string.please help


    Yes. First learn that C++ and C are different languages, so posting to
    comp.lang.c++ is entirely inappropriate if you want a C solution.

    Having excluded comp.lang.c++ you should first try to write your
    algorithm. comp.lang.c does not generally help with algorithms,
    comp.programming and alt.comp.lang.c-c++ might, check the groups out to
    see. comp.lang.c discusses the C language and helps people with C problems.

    Then, post specific questions rather than just asking someone to help
    you writing it. A lot of us could write the function in less time that
    it would take to explain it to you, but this would not help you to learn.

    If you don't know where to start, then I suggest you start off by trying
    to write all the permutations of a short string by hand rather than
    trying to write a program to do it. Then you can analyse how you did it
    and try to formalise that in to an algorithm.

    I've excluded comp.lang.c++ from the follow-ups. When you have decided
    whether you have a problem with the C language or with writing the
    algorithm please cut the posting down to only the most appropriate group.
    --
    Flash Gordon, living in interesting times.
    Web site - http://home.flash-gordon.me.uk/
    comp.lang.c posting guidelines and intro:
    http://clc-wiki.net/wiki/Intro_to_clc
     
    Flash Gordon, Jul 20, 2006
    #3
  4. anurag

    Lew Pitcher Guest

    -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1


    anurag wrote:
    > hey can anyone help me in writing a code in c (function) that prints
    > all permutations of a string.please help


    IIRC, this favour has been requested a number of times in recent weeks.
    I wonder why the sudden interest in permuting strings using C
    functions.

    In any case, to give a concrete example of what R.H. discusses
    elsethread, here's an attempt I made a few weeks ago, when the question
    first came up. Take it as you will.

    For the regulars: yes I know that answering a homework question is
    frowned apon, and even worse is answering an algorithm question, but
    this one piqued my interest. So, for my one freebie a year, I post this
    code ;-)

    ==snip==

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    void rotate(unsigned length, char *string)
    {
    char save;

    save = *string;
    while(--length)
    {
    *string=*(string+1);
    ++string;
    }
    *string = save;
    }

    void permute(unsigned length, char *string, unsigned depth)
    {

    if (length == 0)
    printf("%s\n",string-depth);
    else
    {
    unsigned count;

    for (count = length ; count > 0; --count)
    {
    permute(length-1,string+1,depth+1);
    rotate(length,string);
    }
    }

    }


    int main(int argc, char **argv)
    {
    while (--argc)
    {
    char *source = malloc(strlen(*++argv)+1);

    if (source)
    {
    strcpy(source,*argv);
    printf("\nPermuting \"%s\"\n",source);

    permute(strlen(source),source,0);

    free(source);
    }
    }
    return EXIT_SUCCESS;
    }


    ==snip==

    - --
    Lew Pitcher


    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.3 (MingW32) - WinPT 0.11.12

    iD8DBQFEv84lagVFX4UWr64RAq3YAKDBs4//FGSrc+zn7+duG2bRtCuRaQCfSnOS
    mg6QbOGNExUVVsXBp5lQYD8=
    =pYBy
    -----END PGP SIGNATURE-----
     
    Lew Pitcher, Jul 20, 2006
    #4
  5. In article <>,
    anurag <> writes
    >hey can anyone help me in writing a code in c (function) that prints
    >all permutations of a string.please help
    >


    That looks like homework. In addition it is under specified. Are the
    characters in the string all unique or are repeats allowed? If they are
    all unique it is very easy :)

    --
    Francis Glassborow ACCU
    Author of 'You Can Do It!' and "You Can Program in C++"
    see http://www.spellen.org/youcandoit
    For project ideas and contributions: http://www.spellen.org/youcandoit/projects
     
    Francis Glassborow, Jul 20, 2006
    #5
  6. Francis Glassborow <> writes:
    > In article <>,
    > anurag <> writes
    >>hey can anyone help me in writing a code in c (function) that prints
    >>all permutations of a string.please help
    >>

    >
    > That looks like homework. In addition it is under specified. Are the
    > characters in the string all unique or are repeats allowed? If they
    > are all unique it is very easy :)


    Not as easy as if they're all the same!

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Jul 20, 2006
    #6
  7. anurag

    Noah Roberts Guest

    anurag wrote:
    > hey can anyone help me in writing a code in c (function) that prints
    > all permutations of a string.please help


    Knuth, Volume 4 fascicle 2.
     
    Noah Roberts, Jul 20, 2006
    #7
  8. * Noah Roberts:
    > anurag wrote:
    >> hey can anyone help me in writing a code in c (function) that prints
    >> all permutations of a string.please help

    >
    > Knuth, Volume 4 fascicle 2.


    As I recall, Knuth does not discuss or mention arithmetic coding of
    permutations (using the factorial number system), so is not a complete
    reference.

    --
    A: Because it messes up the order in which people normally read text.
    Q: Why is it such a bad thing?
    A: Top-posting.
    Q: What is the most annoying thing on usenet and in e-mail?
     
    Alf P. Steinbach, Jul 20, 2006
    #8
  9. anurag

    Ben Pfaff Guest

    "Alf P. Steinbach" <> writes:

    > * Noah Roberts:
    >> anurag wrote:
    >>> hey can anyone help me in writing a code in c (function) that prints
    >>> all permutations of a string.please help

    >> Knuth, Volume 4 fascicle 2.

    >
    > As I recall, Knuth does not discuss or mention arithmetic coding of
    > permutations (using the factorial number system), so is not a complete
    > reference.


    Is that necessary to answer the OP's question? I doubt it.
    --
    "doe not call up Any that you can not put downe."
    --H. P. Lovecraft
     
    Ben Pfaff, Jul 20, 2006
    #9
  10. anurag

    Jon Clements Guest

    Francis Glassborow wrote:
    > In article <>,
    > anurag <> writes
    > >hey can anyone help me in writing a code in c (function) that prints
    > >all permutations of a string.please help
    > >

    >
    > That looks like homework. <snip>


    (cross postings removed)

    Strange, was a huge interest in this in comp.lang.python as well - just
    the other week. Must be that bit of the course they've all gotten to!

    Jon
     
    Jon Clements, Jul 20, 2006
    #10
  11. Lew Pitcher wrote:
    >
    > -----BEGIN PGP SIGNED MESSAGE-----
    > Hash: SHA1
    >
    > anurag wrote:
    > > hey can anyone help me in writing a code in c (function) that prints
    > > all permutations of a string.please help

    >
    > IIRC, this favour has been requested a number of times in recent weeks.
    > I wonder why the sudden interest in permuting strings using C
    > functions.


    Perhaps from summer school assignments from all those students who
    failed their C classes?

    [...]


    --
    +-------------------------+--------------------+-----------------------+
    | Kenneth J. Brody | www.hvcomputer.com | #include |
    | kenbrody/at\spamcop.net | www.fptech.com | <std_disclaimer.h> |
    +-------------------------+--------------------+-----------------------+
    Don't e-mail me at: <mailto:>
     
    Kenneth Brody, Jul 21, 2006
    #11
  12. anurag

    Noah Roberts Guest

    Alf P. Steinbach wrote:
    > * Noah Roberts:
    > > anurag wrote:
    > >> hey can anyone help me in writing a code in c (function) that prints
    > >> all permutations of a string.please help

    > >
    > > Knuth, Volume 4 fascicle 2.

    >
    > As I recall, Knuth does not discuss or mention arithmetic coding of
    > permutations (using the factorial number system), so is not a complete
    > reference.


    Yeah, I don't know what's actually in it. I have it but haven't gotten
    the time to read it yet. Knuth takes me an extraordinary amount of
    time to read. But it's title is "Generating all permutations and
    combinations" so I figured it would be appropriate. Guy might learn
    something instead of having his homework done for him.
     
    Noah Roberts, Jul 21, 2006
    #12
  13. anurag

    Simon Biber Guest

    Alf P. Steinbach wrote:
    > * Noah Roberts:
    >> anurag wrote:
    >>> hey can anyone help me in writing a code in c (function) that prints
    >>> all permutations of a string.please help

    >>
    >> Knuth, Volume 4 fascicle 2.

    >
    > As I recall, Knuth does not discuss or mention arithmetic coding of
    > permutations (using the factorial number system), so is not a complete
    > reference.


    When you refer to arithmetic coding of permutations using the factorial
    number system, are you talking about an algorithm that assigns a unique
    index number to each permutation and can return any individual
    permutation given its index number?

    I have implemented a system like that below:

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    typedef unsigned long long ull;

    /* calculate factorial of given number */
    ull fact(ull a)
    {
    ull result = 1;
    while(a) result *= a--;
    return result;
    }

    /* generates a permutation of str and stores it in 'rs'
    the permutation generated is index number 'no'
    of 'np' total permutations (np == fact(strlen(str)) */
    void get_perm(char *rs, const char *str, ull no, ull np)
    {
    size_t len = strlen(str);
    ull nm = no;
    ull lt;
    char *p;
    char temp;
    strcpy(rs, str);

    for(p = rs; *p; p++)
    {
    np = np / len;
    lt = nm / np;
    nm = nm % np;

    temp = p[0];
    p[0] = p[lt];
    p[lt] = temp;

    len--;
    }
    }

    void print_all(const char *str)
    {
    size_t len = strlen(str);
    char *rs = malloc(len + 1);
    ull np = fact(len);
    ull i;
    if(!rs)
    {
    fprintf(stderr, "Error allocating memory\n");
    }
    else for(i = 0; i < np; i++)
    {
    get_perm(rs, str, i, np);
    printf("%4lld: %s\n", i, rs);
    }
    }

    int main(int argc, char **argv)
    {
    if(argc == 2)
    {
    print_all(argv[1]);
    }
    else
    {
    fprintf(stderr, "Error: require one argument for"
    " string to permute\n");
    }
    return 0;
    }
     
    Simon Biber, Jul 21, 2006
    #13
  14. Lew Pitcher wrote:
    > For the regulars: yes I know that answering a homework question is
    > frowned apon, and even worse is answering an algorithm question, but
    > this one piqued my interest. So, for my one freebie a year, I post this
    > code ;-)


    The code gives the same amount of permutations for following two cases,
    is it correct?

    Permuting "abcde"
    abcde
    abced
    ....

    Permuting "abcdd"
    abcdd
    abcdd
    ....
     
    lovecreatesbeauty, Jul 25, 2006
    #14
  15. Ben Pfaff wrote:
    > "Alf P. Steinbach" <> writes:
    >
    > > * Noah Roberts:
    > >> anurag wrote:
    > >>> hey can anyone help me in writing a code in c (function) that prints
    > >>> all permutations of a string.please help
    > >> Knuth, Volume 4 fascicle 2.

    > >
    > > As I recall, Knuth does not discuss or mention arithmetic coding of
    > > permutations (using the factorial number system), so is not a complete
    > > reference.

    >
    > Is that necessary to answer the OP's question? I doubt it.
    > --
    > "doe not call up Any that you can not put downe."
    > --H. P. Lovecraft


    Why? Up to now, the code given by you C experts are all wrong. Are you
    all line-shooters?
     
    lovecreatesbeauty, Jul 25, 2006
    #15
  16. anurag

    Ben Pfaff Guest

    "lovecreatesbeauty" <> writes:

    > Why? Up to now, the code given by you C experts are all wrong. Are you
    > all line-shooters?


    Some code I wrote for generating permutations can be found in
    ll_next_permutation and ll_prev_permutation at
    http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/ll.c?rev=1.1&root=pspp&view=markup
    It targets linked lists, not strings.

    There's a test program at
    http://cvs.savannah.gnu.org/viewcvs...t.c?content-type=text/plain&rev=1.1&root=pspp
    --
    int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
    \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
    );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p\
    );}return 0;}
     
    Ben Pfaff, Jul 25, 2006
    #16
  17. anurag

    Ivanna Pee Guest

    Lew Pitcher wrote:
    > -----BEGIN PGP SIGNED MESSAGE-----
    > Hash: SHA1
    >
    >
    > anurag wrote:
    > > hey can anyone help me in writing a code in c (function) that prints
    > > all permutations of a string.please help

    >
    > IIRC, this favour has been requested a number of times in recent weeks.
    > I wonder why the sudden interest in permuting strings using C
    > functions.
    >
    > In any case, to give a concrete example of what R.H. discusses
    > elsethread, here's an attempt I made a few weeks ago, when the question
    > first came up. Take it as you will.
    >
    > For the regulars: yes I know that answering a homework question is
    > frowned apon, and even worse is answering an algorithm question, but
    > this one piqued my interest. So, for my one freebie a year, I post this
    > code ;-)
    >
    > ==snip==
    >
    > #include <stdio.h>
    > #include <stdlib.h>
    > #include <string.h>
    >
    > void rotate(unsigned length, char *string)
    > {
    > char save;
    >
    > save = *string;
    > while(--length)
    > {
    > *string=*(string+1);
    > ++string;
    > }
    > *string = save;
    > }
    >
    > void permute(unsigned length, char *string, unsigned depth)
    > {
    >
    > if (length == 0)
    > printf("%s\n",string-depth);
    > else
    > {
    > unsigned count;
    >
    > for (count = length ; count > 0; --count)
    > {
    > permute(length-1,string+1,depth+1);
    > rotate(length,string);
    > }
    > }
    >
    > }
    >
    >
    > int main(int argc, char **argv)
    > {
    > while (--argc)
    > {
    > char *source = malloc(strlen(*++argv)+1);
    >
    > if (source)
    > {
    > strcpy(source,*argv);
    > printf("\nPermuting \"%s\"\n",source);
    >
    > permute(strlen(source),source,0);
    >
    > free(source);
    > }
    > }
    > return EXIT_SUCCESS;
    > }
    >
    >
    > ==snip==
    >
    > - --
    > Lew Pitcher
    >
    >
    > -----BEGIN PGP SIGNATURE-----
    > Version: GnuPG v1.4.3 (MingW32) - WinPT 0.11.12
    >
    > iD8DBQFEv84lagVFX4UWr64RAq3YAKDBs4//FGSrc+zn7+duG2bRtCuRaQCfSnOS
    > mg6QbOGNExUVVsXBp5lQYD8=
    > =pYBy
    > -----END PGP SIGNATURE-----


    Now try it recursively.
     
    Ivanna Pee, Jul 25, 2006
    #17
  18. anurag

    Mark P Guest

    Noah Roberts wrote:
    > anurag wrote:
    >> hey can anyone help me in writing a code in c (function) that prints
    >> all permutations of a string.please help

    >
    > Knuth, Volume 4 fascicle 2.
    >


    Based on their source I assume these are "legal" links to the pre-fascicles:

    http://www.cs.utsa.edu/~wagner/knuth/

    -Mark
     
    Mark P, Jul 25, 2006
    #18
  19. anurag

    karteek007

    Joined:
    Apr 17, 2009
    Messages:
    1
    Need Help

    >>Lew Pitcher

    Can you please explain me the algorithm for this program that you gave :captain:

    I always confuse when writing recursive programs, please help me with this.

    Thank you,
     
    karteek007, Apr 17, 2009
    #19
    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. Girish Sahani
    Replies:
    11
    Views:
    1,640
    Boris Borcic
    Jun 26, 2006
  2. Maric Michaud
    Replies:
    0
    Views:
    389
    Maric Michaud
    Jun 22, 2006
  3. anurag

    print all permutations of string

    anurag, Jul 20, 2006, in forum: C Programming
    Replies:
    20
    Views:
    1,763
    Mark P
    Jul 25, 2006
  4. Shraddha

    How to print permutations?

    Shraddha, May 25, 2007, in forum: C++
    Replies:
    5
    Views:
    385
    John Harrison
    May 26, 2007
  5. sanket
    Replies:
    3
    Views:
    520
Loading...

Share This Page