Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uunet!willett!ForthNet
From: ForthNet@willett.UUCP (ForthNet articles from GEnie)
Newsgroups: comp.lang.forth
Subject: PUZZLES AND PROBLEMS
Message-ID: <1270.UUL1.3#5129@willett.UUCP>
Date: 4 Jul 90 01:45:46 GMT
Organization: Latest link in the ForthNet chain.  (Pgh, PA)
Lines: 80

Category 3,  Topic 35
Message 122       Tue Jul 03, 1990
W.BADEN1 [Wil]               at 18:31 PDT
 
My apologies for the Permutation Puzzle.  When I posed it I thought that there
was a simple solution.

Two days after discovering my solution I found the standard algorithm for this
by H. F. Trotter, Algorithm 115, C.A.C.M., August 1962.  The two produce
exactly the same sequence.  I don't expect that I'm the first to solve it the
way I have, and if any one seen this solution before, would you let me know? 
I wish I had thought of it 30 or even 20 years ago, though.

Trotter's algorithm was written in spaghetti Algol. (Sounds tasty -- spaghetti
al gol.)  Here are C versions of my algorithm and his for comparison.

 W.Baden.

 int commuted( int n, long i )
 {
    int k, q;
    if ( !i )
        return 0;
    k = 0;
    while ( !( q = i % n ) && n > 1 )
        if ( !(( i /= n-- ) & 1 ))
            k++;
    if ( ( i / n ) & 1 )
        q = n - q;
    return q + k;
 }

 H. F. Trotter

 #define MAXPERM 10
 static int p[ MAXPERM ] = { 1 };
 static int d[ MAXPERM ];
 int perm( int n )
 {
    int k, q;
    if ( p[ 0 ] )
    {
        for ( k = 0; k < n; k++ )
        {
            p[ k ] = 0;
            d[ k ] = 1;
        }
        return 0;
    }
    k = 0;
    --n;
    do
    {
        if ( !( q = p[ n ] += d[ n ]) )
        {
            d[ n ] = 1;
            k++;
        }
        else
        {
            if ( q <= n )
                return k + q; /* The usual exit.*/
            d[ n ] = -1;
        }
    } while ( --n ); /* The final exit.*/
    p[ 0 ] = 1;
    return k + 1;
 }

If you don't know C well you'll probably have trouble following my algorithm,
but you should be able to understand Trotter's.  As a previous posting showed,
there is a reasonable Forth implementation of my algorithm.  I won't even try
to forthify Trotter's, unless I need lots of speed for this function.

Once again, is Forth a suitable language for this kind of problem?

Procedamus in pace.
-----
This message came from GEnie via willett through a semi-automated process.
Report problems to: uunet!willett!dwp or willett!dwp@hobbes.cert.sei.cmu.edu