Richard Heathfield's TSP permutation algorithm

Discussion in 'C Programming' started by whitehatmiracle@gmail.com, Sep 16, 2006.

  1. Guest

    Dear Sir I couldnt quite figure out wat your permute function does
    exactly... could you please throw some light on it?
    void Permute(char *Perm,
    size_t n,
    size_t unchanged)
    {
    size_t outer = 0;
    size_t inner = 0;
    int temp = 0;


    if(unchanged < n)
    {
    for(outer = unchanged; outer < n; outer++)
    {
    temp = Perm[outer];
    for(inner = outer; inner > unchanged; inner--)
    {
    Perm[inner] = Perm[inner - 1];
    }
    Perm[unchanged] = temp;
    Permute(Perm,
    n,
    unchanged + 1);


    for(inner = unchanged; inner < outer; inner++)
    {
    Perm[inner] = Perm[inner + 1];
    }
    Perm[outer] = temp;
    }
    }
    else
    {
    printf("%s\n", Perm);
    }



    }


    int main(int argc, char **argv)
    {
    char Input[256] = {0};
    size_t len = 0;

    if(argc > 1)
    {
    len = strlen(argv[1]);
    if(len > sizeof Input - 1)
    {
    fprintf(stderr, "word too long for demo - truncating\n");
    argv[1][sizeof Input - 1] = '\0';
    }
    strcpy(Input, argv[1]);
    len = strlen(Input);
    }
    else
    {
    len = 3;
    strcpy(Input, "ABC");
    }


    Permute(Input, len, 0);


    return 0;

    }

    Thanking you
    The whitehat
    , Sep 16, 2006
    #1
    1. Advertising

  2. said:

    > Dear Sir I couldnt quite figure out wat your permute function does
    > exactly... could you please throw some light on it?


    It just permutes an array. If you want to turn it into a brute-forcer, I
    suggest you hack it to accept a function that will be called whenever a
    permutation is found.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
    Richard Heathfield, Sep 16, 2006
    #2
    1. Advertising

  3. Guest

    What does inner outer and unchanged do?
    , Sep 17, 2006
    #3
  4. said:

    > What does inner outer and unchanged do?


    Partition the array into two parts, an empty part, and the part you want to
    permute.

    | ABCDE

    Move each element on the right-hand side to the left-hand side, in turn.

    A | BCDE
    B | CDEA
    C | DEAB
    D | EABC
    E | ABCD

    All you're really doing is rotating the array, yes?

    For each of those partitioned array arrangements, we now have to solve the
    problem of permuting the right-hand side, and incorporating the left-hand
    side, ***unchanged***, into the final result.

    Take A | BCDE, for example. We have 1 unchanged element, which will prefix
    each solution, and an array, BCDE. We can solve this problem by recursing.
    How? Well, like this...

    Move each element on the right-hand side to the left-hand side, in turn.

    AB | CDE
    AC | DEB
    AD | EBC
    AE | BCD

    All you're really doing is rotating the BCDE part of the array, yes?

    For each of those partitioned array arrangements, we now have to solve the
    problem of permuting the right-hand side, and incorporating the left-hand
    side, ***unchanged***, into the final result.

    Take AB | CDE, for example. We have 2 unchanged elements, which will prefix
    each solution, and an array, CDE. We can solve this problem by recursing.
    How? Well, like this...

    Move each element on the right-hand side to the left-hand side, in turn.

    ABC | DE
    ABD | EC
    ABE | CD

    All you're really doing is rotating the CDE part of the array, yes?

    For each of those partitioned array arrangements, we now have to solve the
    problem of permuting the right-hand side, and incorporating the left-hand
    side, ***unchanged***, into the final result.

    Take ABC | DE, for example. We have 3 unchanged elements, which will prefix
    each solution, and an array, DE. We can solve this problem by recursing.
    How? Well, like this...

    Move each element on the right-hand side to the left-hand side, in turn.

    ABCD | E
    ABCE | D

    All you're really doing is rotating the DE part of the array, yes?

    For each of those partitioned array arrangements, we now have to solve the
    problem of permuting the right-hand side, and incorporating the left-hand
    side, ***unchanged***, into the final result. But since each right-hand
    side only has 1 element therein, there is only one permutation.

    So for each of them we just display the result. ABCDE, and ABCED.

    Then we drop out of this recursion, and continue with the next, and so on
    until everything is done.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
    Richard Heathfield, Sep 17, 2006
    #4
  5. CBFalconer Guest

    Richard Heathfield wrote:
    > said:
    >
    >> What does inner outer and unchanged do?

    >
    > Partition the array into two parts, an empty part, and the part
    > you want to permute.
    >
    > | ABCDE
    >
    > Move each element on the right-hand side to the left-hand side,
    > in turn.
    >
    > A | BCDE
    > B | CDEA
    > C | DEAB
    > D | EABC
    > E | ABCD
    >
    > All you're really doing is rotating the array, yes?
    >
    > For each of those partitioned array arrangements, we now have to
    > solve the problem of permuting the right-hand side, and incorporating
    > the left-hand side, ***unchanged***, into the final result.
    >
    > Take A | BCDE, for example. We have 1 unchanged element, which will
    > prefix each solution, and an array, BCDE. We can solve this problem
    > by recursing. How? Well, like this...
    >
    > Move each element on the right-hand side to the left-hand side,
    > in turn.
    >
    > AB | CDE
    > AC | DEB
    > AD | EBC
    > AE | BCD
    >
    > All you're really doing is rotating the BCDE part of the array, yes?
    >
    > For each of those partitioned array arrangements, we now have to solve
    > the problem of permuting the right-hand side, and incorporating the
    > left-hand side, ***unchanged***, into the final result.
    >
    > Take AB | CDE, for example. We have 2 unchanged elements, which will
    > prefix each solution, and an array, CDE. We can solve this problem
    > by recursing. How? Well, like this...
    >
    > Move each element on the right-hand side to the left-hand side, in
    > turn.
    >
    > ABC | DE
    > ABD | EC
    > ABE | CD
    >
    > All you're really doing is rotating the CDE part of the array, yes?
    >
    > For each of those partitioned array arrangements, we now have to
    > solve the problem of permuting the right-hand side, and incorporating
    > the left-hand side, ***unchanged***, into the final result.
    >
    > Take ABC | DE, for example. We have 3 unchanged elements, which will
    > prefix each solution, and an array, DE. We can solve this problem by
    > recursing. How? Well, like this...
    >
    > Move each element on the right-hand side to the left-hand side, in
    > turn.
    >
    > ABCD | E
    > ABCE | D
    >
    > All you're really doing is rotating the DE part of the array, yes?
    >
    > For each of those partitioned array arrangements, we now have to
    > solve the problem of permuting the right-hand side, and
    > incorporating the left-hand side, ***unchanged***, into the final
    > result. But since each right-hand side only has 1 element therein,
    > there is only one permutation.
    >
    > So for each of them we just display the result. ABCDE, and ABCED.
    >
    > Then we drop out of this recursion, and continue with the next,
    > and so on until everything is done.


    And that very nice description applies equally to my 'jumble'
    routine, which I published here earlier as a complete program.
    Jumble also allows you to suppress any output past a preselected
    length value.

    Richards description, and my lack of one, illustrates why I do not
    make a good teacher. I am repeating my actual heart code for
    illustration below:

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

    --
    "The most amazing achievement of the computer software industry
    is its continuing cancellation of the steady and staggering
    gains made by the computer hardware industry..." - Petroski



    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Sep 17, 2006
    #5
  6. Guest

    WOW
    Thanx a millions to Mr Richard Heathfield and to Mr CBFalconer
    Now both your algorithms are clear, and even the ideas are clearer.

    Thanx once again......
    , Sep 18, 2006
    #6
  7. Guest

    Just one last clarification:

    for
    A | BCDE
    B | CDEA
    inner is the right hand side of the bar |?
    and outer is it the left hand side of the | bar?

    The external most for loop does it permute only the first letter of the
    combination??


    if(unchanged < n)
    {
    for(outer = unchanged; outer < n; outer++)
    {
    temp = Perm[outer];
    for(inner = outer; inner > unchanged; inner--)
    {
    Perm[inner] = Perm[inner - 1];
    }
    Perm[unchanged] = temp;
    Permute(Perm,
    n,
    unchanged + 1);


    for(inner = unchanged; inner < outer; inner++)
    {
    Perm[inner] = Perm[inner + 1];
    }
    Perm[outer] = temp;
    }
    }
    else
    {
    printf("%s\n", Perm);
    }
    , Sep 20, 2006
    #7
  8. said:

    > Just one last clarification:
    >
    > for
    > A | BCDE
    > B | CDEA
    > inner is the right hand side of the bar |?
    > and outer is it the left hand side of the | bar?


    No. You leave everything to the left of the bar alone.

    > The external most for loop does it permute only the first letter of the
    > combination??


    Nothing special about it at all. It just rotates the array and then recurses
    to permute each rotation in turn.

    > if(unchanged < n)


    Have we finished yet? No? Okay, let's rotate the array...

    > {
    > for(outer = unchanged; outer < n; outer++)
    > {
    > temp = Perm[outer];
    > for(inner = outer; inner > unchanged; inner--)
    > {
    > Perm[inner] = Perm[inner - 1];
    > }
    > Perm[unchanged] = temp;


    This bit changes, say, BCDE into EBCD

    > Permute(Perm,
    > n,
    > unchanged + 1);


    This bit submits AEBCD to recursion.

    > for(inner = unchanged; inner < outer; inner++)
    > {
    > Perm[inner] = Perm[inner + 1];
    > }
    > Perm[outer] = temp;


    And this bit jiggles the array back into the right order so that the next
    recursion level up from here works properly.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
    Richard Heathfield, Sep 20, 2006
    #8
  9. Guest

    So actually what would be the appropriate name for outer and inner?
    , Sep 21, 2006
    #9
  10. said:

    > So actually what would be the appropriate name for outer and inner?


    In the absence of contextual information to the contrary, the most
    appropriate name for outer is outer.

    In the absence of contextual information to the contrary, the most
    appropriate name for inner is inner.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
    Richard Heathfield, Sep 21, 2006
    #10
  11. writes:
    > So actually what would be the appropriate name for outer and inner?


    Please provide context. See <http://cfaj.freeshell.org/google/>.
    (The bug in Google Groups has been corrected, so it's even easier to
    get this right.)

    --
    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, Sep 21, 2006
    #11
  12. CBFalconer Guest

    Richard Heathfield wrote:
    > said:
    >
    >> So actually what would be the appropriate name for outer and inner?

    >
    > In the absence of contextual information to the contrary, the most
    > appropriate name for outer is outer.
    >
    > In the absence of contextual information to the contrary, the most
    > appropriate name for inner is inner.


    This is probably a discussion of naval strategy. In the UK, direct
    the questions to the Admiralty. Try the First Sea Lord. In the
    US, try the Department of the Navy.

    --
    Some informative links:
    news:news.announce.newusers
    http://www.geocities.com/nnqweb/
    http://www.catb.org/~esr/faqs/smart-questions.html
    http://www.caliburn.nl/topposting.html
    http://www.netmeister.org/news/learn2quote.html



    --
    Posted via a free Usenet account from http://www.teranews.com
    CBFalconer, Sep 21, 2006
    #12
  13. Guest

    Sorry for the netiquette:
    I meant
    >> size_t outer = 0;
    >> size_t inner = 0;

    what would be the approproate name for inner and outer?


    > This is probably a discussion of naval strategy. In the UK, direct
    > the questions to the Admiralty. Try the First Sea Lord. In the
    > US, try the Department of the Navy.


    OMG Hahahahaaa nice one
    , Sep 22, 2006
    #13
    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. Malcolm McLean

    Richard Heathfield's personal threads.

    Malcolm McLean, Nov 9, 2007, in forum: C Programming
    Replies:
    52
    Views:
    1,181
    Christopher Benson-Manica
    Nov 21, 2007
  2. Tomás Ó hÉilidhe

    [OFF-TOPIC] Animosity on the part of Mr Richard Heathfield

    Tomás Ó hÉilidhe, Dec 13, 2008, in forum: C Programming
    Replies:
    113
    Views:
    2,002
    Richard Bos
    Dec 22, 2008
  3. Anonymous

    Animosity on the part of Mr Richard Heathfield

    Anonymous, Dec 14, 2008, in forum: C Programming
    Replies:
    6
    Views:
    389
    CBFalconer
    Dec 21, 2008
  4. Borked Pseudo Mailed

    Animosity on the part of Mr Richard Heathfield

    Borked Pseudo Mailed, Dec 14, 2008, in forum: C Programming
    Replies:
    0
    Views:
    227
    Borked Pseudo Mailed
    Dec 14, 2008
  5. Anonymous

    Animosity on the part of Mr Richard Heathfield

    Anonymous, Dec 14, 2008, in forum: C Programming
    Replies:
    0
    Views:
    271
    Anonymous
    Dec 14, 2008
Loading...

Share This Page