variable length permutation code

Discussion in 'C Programming' started by Robert Hayes, Jan 28, 2012.

  1. Robert Hayes

    Robert Hayes Guest

    I have code that will take a string and generate the permutations of
    the string. i.e. the string is abc:
    abc
    acb
    bac
    bca
    cab
    cba

    What I would like is to modify it so it can produce:
    a
    b
    c
    ab
    ac
    ba
    bc
    ca
    cb
    abc
    acb
    bac
    bca
    cab
    cba

    I would like to work this out for myself so all I would like is some
    pseudo code please.

    Thanks,
     
    Robert Hayes, Jan 28, 2012
    #1
    1. Advertising

  2. Robert Hayes

    Stefan Ram Guest

    Robert Hayes <> writes:
    >I would like to work this out for myself so all I would like is some
    >pseudo code please.


    What about

    p( "a" ); p( "ab" ); p( "abc" );

    ?
     
    Stefan Ram, Jan 29, 2012
    #2
    1. Advertising

  3. -berlin.de (Stefan Ram) writes:

    > Robert Hayes <> writes:
    >>I would like to work this out for myself so all I would like is some
    >>pseudo code please.

    >
    > What about
    >
    > p( "a" ); p( "ab" ); p( "abc" );


    and p("b"); p("c"); p("ac"); p("bc");

    --
    Ben.
     
    Ben Bacarisse, Jan 29, 2012
    #3
  4. Robert Hayes

    Stefan Ram Guest

    Ben Bacarisse <> writes:
    >-berlin.de (Stefan Ram) writes:
    >>Robert Hayes <> writes:
    >>>I would like to work this out for myself so all I would like is some
    >>>pseudo code please.

    >>What about
    >>p( "a" ); p( "ab" ); p( "abc" );

    >and p("b"); p("c"); p("ac"); p("bc");


    Yes, thank you. I have posted slightly more general code at

    http://www.purl.org/stefan_ram/ascii/perm.c

    . It is not pseudo code, but it is so hard to understand,
    that Robert will still have enough to do when he tries to
    understand how it works.
     
    Stefan Ram, Jan 29, 2012
    #4
  5. Robert Hayes

    Gene Guest

    On Jan 28, 4:03 pm, Robert Hayes <> wrote:
    > I have code that will take a string and generate the permutations of
    > the string.  i.e.  the string is abc:
    > abc
    > acb
    > bac
    > bca
    > cab
    > cba
    >
    > What I would like is to modify it so it can produce:
    > a
    > b
    > c
    > ab
    > ac
    > ba
    > bc
    > ca
    > cb
    > abc
    > acb
    > bac
    > bca
    > cab
    > cba
    >
    > I would like to work this out for myself so all I would like is some
    > pseudo code please.
    >
    > Thanks,


    If you don't want the C, then this isn't really a C question, but
    okay...

    It looks like you want to compose two algorithms, finding all
    permutations of all combinations. You already how how to do the
    first. To enumerate the combinations of n things taken m at a time,
    an easy algorithm is to choose each item i = 0 to n-m in succession
    and then recursively choose m-1 items from the remaining items in the
    range i+1 to n-1. The base cases are straightforward: When m>n, do
    nothing. This is impossible. When m==0, output all choices thus
    far. In this case rather than producing the combination as output
    immediately, you'll be feeding the combination to your permutation
    generator.
     
    Gene, Jan 29, 2012
    #5
  6. Gene <> wrote:
    > Robert Hayes <> wrote:
    > > I have code that will take a string and generate the permutations
    > > of the string. [...snip...]
    > > What I would like is to modify it so it can produce:
    > > a
    > > b
    > > c
    > > ab
    > > ac
    > > ba
    > > bc
    > > ca
    > > cb
    > > abc
    > > acb
    > > bac
    > > bca
    > > cab
    > > cba
    > >
    > > I would like to work this out for myself so all I would like
    > > is some pseudo code please.

    >
    > If you don't want the C, then this isn't really a C question,
    > but okay...
    >
    > It looks like you want to compose two algorithms, finding all
    > permutations of all combinations.  You already how how to do
    > the first.  To enumerate the combinations of n things taken m
    > at a time, an easy algorithm is to choose each item i = 0 to
    > n-m in succession and then recursively choose m-1 items from
    > the remaining items in the range i+1 to n-1. The base cases
    > are straightforward:  When m>n, do nothing. This is impossible.
    > When m==0, output all choices thus far.  In this case rather
    > than producing the combination as output immediately, you'll
    > be feeding the combination to your permutation generator.


    If you have repeated letters in the original string, you need to
    be careful about duplication. For instance, starting with abaca,
    three selections of two letters produce aa.

    You can avoid this by counting unique letters and recursively
    iterating over those unique letter counts. The code below does
    this by sorting the string and treating repeated letters as one
    block. Apart from that, it's Gene's algorithm.

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

    /* take permute function as read...*/
    void swap(char *p, char *q) { char t = *p; *p = *q; *q = t;
    } void reverse(char *p, char *q) { if (p != q) for(; p <
    --q; p++) swap(p, q); } int permute(char *p, char *q) { char
    *r, *s, *t; if (p == q) return 0; for (r = q - 1; p < r; ) {
    s = r--; if (*r < *s) { t = q; while (*r >= *--t) ; swap(r,
    t); reverse(s, q); return 1; } } reverse(p, q); return 0; }

    void dist(char *sub, size_t i, size_t n, char *curr)
    {
    if (i == n)
    {
    sub[n] = 0;
    do { puts(sub); } while (permute(sub, sub + n));
    }
    else if (strlen(curr) < n - i)
    return;
    else
    {
    size_t c, d, z;
    char *next = strrchr(curr, *curr) + 1;
    z = next - curr;
    if (n - i < z) z = n - i;

    for (d = 0; d < z; d++)
    sub[i + d] = *curr;

    for (c = z + 1; c-- > 0; )
    dist(sub, i + c, n, next);
    }
    }

    int cmp(const void *lv, const void *rv)
    {
    const char *lc = lv;
    const char *rc = rv;
    return (*lc > *rc) - (*lc < *rc);
    }

    int main(int argc, char **argv)
    {
    char sub[42]; /* big enough! */

    if (argc > 1)
    while (argv++, --argc)
    {
    size_t n, z = strlen(*argv);

    printf("\n%s:\n", *argv);
    if (sizeof(sub) - 1 < z) { puts("too long!"); continue; }

    qsort(*argv, z, 1, cmp);
    for (n = 1; n <= z; n++)
    dist(sub, 0, n, *argv);
    }

    return 0;
    }

    % acc pc.c -o pc.exe

    % pc abc aaabb

    abc:
    a
    b
    c
    ab
    ba
    ac
    ca
    bc
    cb
    abc
    acb
    bac
    bca
    cab
    cba

    aaabb:
    a
    b
    aa
    ab
    ba
    bb
    aaa
    aab
    aba
    baa
    abb
    bab
    bba
    aaab
    aaba
    abaa
    baaa
    aabb
    abab
    abba
    baab
    baba
    bbaa
    aaabb
    aabab
    aabba
    abaab
    ababa
    abbaa
    baaab
    baaba
    babaa
    bbaaa

    %

    --
    Peter
     
    Peter Nilsson, Jan 31, 2012
    #6
    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:
    616
    D.F.S.
    Sep 26, 2003
  2. m sergei
    Replies:
    4
    Views:
    11,162
    Philip Parker
    Jun 29, 2004
  3. permutation code.

    , Jul 9, 2006, in forum: C Programming
    Replies:
    4
    Views:
    371
    osmium
    Jul 9, 2006
  4. Haoqi Haoqi
    Replies:
    3
    Views:
    121
    Paul Smith
    Nov 13, 2009
  5. Michael Press

    More help requested on permutation code.

    Michael Press, Mar 24, 2006, in forum: Perl Misc
    Replies:
    8
    Views:
    154
    Michael Press
    Mar 30, 2006
Loading...

Share This Page