Permutations of a String

Discussion in 'C Programming' started by Kiran Dalvi, Apr 6, 2004.

  1. Kiran Dalvi

    Kiran Dalvi Guest

    Hi,
    Can anybody please suggest me an efficient approach to find out all
    possible permutations of a String.
    e.g. My input string = "ABC".
    My program should give an output like ....
    ABC, ACB, BAC, BCA, CAB, CBA

    Thanks,
    Kiran
    Kiran Dalvi, Apr 6, 2004
    #1
    1. Advertising

  2. Kiran Dalvi

    Eric Sosman Guest

    Kiran Dalvi wrote:
    >
    > Hi,
    > Can anybody please suggest me an efficient approach to find out all
    > possible permutations of a String.
    > e.g. My input string = "ABC".
    > My program should give an output like ....
    > ABC, ACB, BAC, BCA, CAB, CBA


    There are at least two things wrong with your question:

    - It's not about the C language, but about an algorithm.

    - It stinks to high heaven of homework.

    That said, here's a solution:

    #include <stdio.h>
    #include <string.h>
    int main(int argc, char **argv) {
    return !!printf(strcmp(argc==2?*++argv:"ABC\n"),"ABC")?
    "I can't do that, Dave\n":"ABC, ACB, BAC, BCA, CAB, CBA\n"));
    }

    It might be possible to improve on this solution. One
    avenue of exploration would be to consider the principle of
    mathematical induction: You probably know how to generate
    all the permutations of a one-letter string. Now if you
    have a method for permuting N-letter strings, can you think
    of a way to generate all the permutations of (N+1)-letter
    strings?

    --
    Eric Sosman, Apr 6, 2004
    #2
    1. Advertising

  3. Kiran Dalvi

    CBFalconer Guest

    Kiran Dalvi wrote:
    >
    > Can anybody please suggest me an efficient approach to find out
    > all possible permutations of a String.
    > e.g. My input string = "ABC".
    > My program should give an output like ....
    > ABC, ACB, BAC, BCA, CAB, CBA


    I just happen to have this lying about. Works nicely in
    conjunction with the following 4dos alias:

    c:\c\jumble>alias jumble
    \c\jumble\jumble %1& | sort | uniq | pr -a -T --columns=8

    *** No two chars are the same in the following string ***
    c:\c\jumble>jumble 0O1l
    string="0O1l", max=24, len=4
    01Ol 01lO 0O1l 0Ol1 0l1O 0lO1 10Ol 10lO
    1O0l 1Ol0 1l0O 1lO0 O01l O0l1 O10l O1l0
    Ol01 Ol10 l01O l0O1 l10O l1O0 lO01 lO10


    ------------- cut for file jumble.c ------------
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>

    /* Things get out of hand when larger than 8 */
    #define MAXWORD 12

    /* ------------------ */

    /* exchange 0th and ith char in wd */
    void trade(char *wd, unsigned int i)
    {
    char c;

    c = *wd;
    *wd = wd;
    wd = c;
    } /* trade */

    /* ------------------ */

    /* Form all n char permutations of the characters in the
    string wd of length lgh into outstring at index ix.
    Output the results to stdout. */
    void jumble(char *wd, unsigned int lgh,
    unsigned int ix, /* output place to fill */
    unsigned int n, /* max out places to fill */
    char *outstring)
    {
    unsigned int i;

    if (0 == n) {
    outstring[ix] = '\0';
    puts(outstring);
    }
    else
    for (i = 0; i < lgh; i++) {
    trade(wd, i); /* nop when (0 == i) */
    outstring[ix] = *wd;
    jumble(wd+1, lgh-1, ix+1, n-1, outstring);
    trade(wd, i); /* restore the wd string */
    }
    } /* jumble */

    /* ------------------ */

    int main(int argc, char *argv[])
    {
    unsigned int n, lgh, min;
    double max;
    char outstring[MAXWORD];

    if (argc < 2) {
    fprintf(stderr,
    "Usage: jumble <baseword> [lgh]\n"
    " where the (optional) lgh specifies the\n"
    " maximum length of the output words\n");
    return 0;
    }
    lgh = strlen(argv[1]);
    if (lgh >= MAXWORD) argv[1][lgh = MAXWORD-1] = '\0';

    min = lgh;
    if ((argc > 2) && (1 == sscanf(argv[2], "%u", &n)))
    if (n && (n <= lgh)) min = n;

    for (n = lgh, max = 1.0; n > (lgh - min); n--)
    max = max * n;

    fprintf(stderr, "string=\"%s\", max=%.0f, len=%u\n",
    argv[1], max, min);

    jumble(argv[1], lgh, 0, min, outstring);
    return 0;
    } /* main */

    --
    Some useful references:
    <http://www.ungerhu.com/jxh/clc.welcome.txt>
    <http://www.eskimo.com/~scs/C-faq/top.html>
    <http://benpfaff.org/writings/clc/off-topic.html>
    CBFalconer, Apr 6, 2004
    #3
  4. (Kiran Dalvi) wrote in message news:<>...
    > Hi,
    > Can anybody please suggest me an efficient approach to find out all
    > possible permutations of a String.
    > e.g. My input string = "ABC".
    > My program should give an output like ....
    > ABC, ACB, BAC, BCA, CAB, CBA


    % type perm2.c
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    void q1(char*q2,char*q3)??<char q4=*q2;*q2=*q3;*q3=q4;??>void q5(
    char*q2,char*q3)??<if(q2!=q3)for(;q2<--q3;q2++)q1(q2,q3);??>int
    q6(char*q2,char*q3)??<char*q7,*q8,*q9;if(q2==q3)return 0;for(q7=
    q3-1;q2<q7;)??<q8=q7--;if(*q7<*q8)??<q9=q3;while(*q7>=*--q9);q1(
    q7,q9);q5(q8,q3);return 1;??>??>q5(q2,q3);return 0;??>int q10(
    const void*q2,const void*q3)??<const char*q11=q2,*q12=q3;return(
    *q11>*q12)-(*q11<*q12);??>int main(int q13,char*q14[])??<size_t
    q15;if(q13!=2)return 0;q15=strlen(q14[1]);qsort(q14[1],q15,1,q10
    );do puts(q14[1]);while(q6(q14[1],q14[1]+q15));return 0;??>

    % acc perm2.c -o perm.exe
    perm2.c: warning: 14 trigraph(s) encountered

    % perm ABC
    ABC
    ACB
    BAC
    BCA
    CAB
    CBA

    % perm 1100
    0011
    0101
    0110
    1001
    1010
    1100

    %

    --
    Peter
    Peter Nilsson, Apr 7, 2004
    #4
  5. Kiran Dalvi

    Ben Pfaff Guest

    (Peter Nilsson) writes:

    > (Kiran Dalvi) wrote in message news:<>...
    >> Hi,
    >> Can anybody please suggest me an efficient approach to find out all
    >> possible permutations of a String.
    >> e.g. My input string = "ABC".
    >> My program should give an output like ....
    >> ABC, ACB, BAC, BCA, CAB, CBA

    >
    > % type perm2.c
    > #include <stdio.h>
    > #include <stdlib.h>
    > #include <string.h>
    >
    > void q1(char*q2,char*q3)??<char q4=*q2;*q2=*q3;*q3=q4;??>void q5(
    > char*q2,char*q3)??<if(q2!=q3)for(;q2<--q3;q2++)q1(q2,q3);??>int
    > q6(char*q2,char*q3)??<char*q7,*q8,*q9;if(q2==q3)return 0;for(q7=
    > q3-1;q2<q7;)??<q8=q7--;if(*q7<*q8)??<q9=q3;while(*q7>=*--q9);q1(
    > q7,q9);q5(q8,q3);return 1;??>??>q5(q2,q3);return 0;??>int q10(
    > const void*q2,const void*q3)??<const char*q11=q2,*q12=q3;return(
    > *q11>*q12)-(*q11<*q12);??>int main(int q13,char*q14[])??<size_t
    > q15;if(q13!=2)return 0;q15=strlen(q14[1]);qsort(q14[1],q15,1,q10
    > );do puts(q14[1]);while(q6(q14[1],q14[1]+q15));return 0;??>


    This would be more impressive if I could permute the lines in the
    program into any order and it would still perform correctly.
    Actually, that's a great idea for an IOCCC entry.
    --
    "...deficient support can be a virtue.
    It keeps the amateurs off."
    --Bjarne Stroustrup
    Ben Pfaff, Apr 7, 2004
    #5
  6. Line-permutable, was re: Permutations of a String

    On Tue, 6 Apr 2004, Ben Pfaff wrote:
    >
    > (Peter Nilsson) writes:
    > >
    > > % type perm2.c
    > > #include <stdio.h>
    > > #include <stdlib.h>
    > > #include <string.h>
    > >
    > > void q1(char*q2,char*q3)??<char q4=*q2;*q2=*q3;*q3=q4;??>void q5(
    > > char*q2,char*q3)??<if(q2!=q3)for(;q2<--q3;q2++)q1(q2,q3);??>int
    > > q6(char*q2,char*q3)??<char*q7,*q8,*q9;if(q2==q3)return 0;for(q7=
    > > q3-1;q2<q7;)??<q8=q7--;if(*q7<*q8)??<q9=q3;while(*q7>=*--q9);q1(
    > > q7,q9);q5(q8,q3);return 1;??>??>q5(q2,q3);return 0;??>int q10(
    > > const void*q2,const void*q3)??<const char*q11=q2,*q12=q3;return(
    > > *q11>*q12)-(*q11<*q12);??>int main(int q13,char*q14[])??<size_t
    > > q15;if(q13!=2)return 0;q15=strlen(q14[1]);qsort(q14[1],q15,1,q10
    > > );do puts(q14[1]);while(q6(q14[1],q14[1]+q15));return 0;??>

    >
    > This would be more impressive if I could permute the lines in the
    > program into any order and it would still perform correctly.
    > Actually, that's a great idea for an IOCCC entry.


    *Really* great! I'll admit it's late and I'm unusually sleepy,
    but I can't even come up with a single example of a non-trivially
    line-permutable program, let alone a non-trivial program that is
    also line-permutable! I mean, not counting

    int main() { puts("foo"); return 0; }
    int i;

    and the like, I can't see any way to construct a line-permutable C
    program at all. Something with line-continuations (\), maybe, where
    'int main' on one line magically turns into 'fooint main' when it's
    permuted before a line ending in 'foo\'. That sort of thing.
    Mad props will go to the first non-trivially permutable program to
    be posted. :)

    -Arthur
    Arthur J. O'Dwyer, Apr 7, 2004
    #6
  7. "Kiran Dalvi" <> wrote in message news:...
    > Hi,
    > Can anybody please suggest me an efficient approach to find out all
    > possible permutations of a String.
    > e.g. My input string = "ABC".
    > My program should give an output like ....
    > ABC, ACB, BAC, BCA, CAB, CBA
    >
    > Thanks,
    > Kiran


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

    void
    string_combi ( char * s, int len )
    {
    int i;
    char tmp;
    static int j;
    static char *p;

    if ( !p )
    p = s;

    for ( i = 1; i <= len; i++ )
    {
    if ( len > 2 )
    string_combi ( s+1, len-1 );
    else
    {
    j++;
    printf ( "%d: %s\t", j, p );
    if ( !( j%10 ) )
    puts ( "" );
    }
    if ( i < len )
    {
    tmp = s[len-i];
    s[len-i] = s[0];
    s[0] = tmp;
    }
    }
    return;
    }

    int
    main()
    {
    char s[50];

    printf("\n Enter String : ");
    scanf("%s%*c", s);
    string_combi ( s, strlen ( s ) );

    return EXIT_SUCCESS;
    }
    Vijay Kumar R Zanvar, Apr 7, 2004
    #7
  8. Re: Line-permutable, was re: Permutations of a String

    "Arthur J. O'Dwyer" <> wrote in message news:<>...
    > On Tue, 6 Apr 2004, Ben Pfaff wrote:
    > >
    > > (Peter Nilsson) writes:
    > > >
    > > > % type perm2.c
    > > > #include <stdio.h>
    > > > #include <stdlib.h>
    > > > #include <string.h>
    > > >
    > > > void q1(char*q2,char*q3)??<char q4=*q2;*q2=*q3;*q3=q4;??>void q5(
    > > > char*q2,char*q3)??<if(q2!=q3)for(;q2<--q3;q2++)q1(q2,q3);??>int
    > > > q6(char*q2,char*q3)??<char*q7,*q8,*q9;if(q2==q3)return 0;for(q7=
    > > > q3-1;q2<q7;)??<q8=q7--;if(*q7<*q8)??<q9=q3;while(*q7>=*--q9);q1(
    > > > q7,q9);q5(q8,q3);return 1;??>??>q5(q2,q3);return 0;??>int q10(
    > > > const void*q2,const void*q3)??<const char*q11=q2,*q12=q3;return(
    > > > *q11>*q12)-(*q11<*q12);??>int main(int q13,char*q14[])??<size_t
    > > > q15;if(q13!=2)return 0;q15=strlen(q14[1]);qsort(q14[1],q15,1,q10
    > > > );do puts(q14[1]);while(q6(q14[1],q14[1]+q15));return 0;??>

    > >
    > > This would be more impressive if I could permute the lines in the
    > > program into any order and it would still perform correctly.
    > > Actually, that's a great idea for an IOCCC entry.

    >
    > *Really* great! I'll admit it's late and I'm unusually sleepy,
    > but I can't even come up with a single example of a non-trivially
    > line-permutable program, let alone a non-trivial program that is
    > also line-permutable!

    [...]
    > Mad props will go to the first non-trivially permutable program to
    > be posted. :)



    Uh, dudes? One of last year's winners did this, and marvelously too.
    Go to http://www.ioccc.org and under "Winning entries" for 2001, look
    for "westley"'s.


    --Mark
    Hegemony Cricket, Apr 12, 2004
    #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. Girish Sahani
    Replies:
    11
    Views:
    1,609
    Boris Borcic
    Jun 26, 2006
  2. Maric Michaud
    Replies:
    0
    Views:
    373
    Maric Michaud
    Jun 22, 2006
  3. String Permutations

    , Apr 28, 2006, in forum: C Programming
    Replies:
    1
    Views:
    323
    Thad Smith
    Apr 29, 2006
  4. anurag

    print all permutations of string

    anurag, Jul 20, 2006, in forum: C Programming
    Replies:
    20
    Views:
    1,681
    Mark P
    Jul 25, 2006
  5. anurag
    Replies:
    18
    Views:
    9,102
    karteek007
    Apr 17, 2009
Loading...

Share This Page