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

Category 3,  Topic 35
Message 121       Sun Jul 01, 1990
W.BADEN1 [Wil]               at 02:59 PDT
 
Thanks to BOB WADA, president of Orange County FIG chapter, for answering the
Permutation Puzzle.  

The puzzle was to generate the permutations of n things with the least effort.
Least effort in this situation means with the least amount of work if the
operations were actually physically performed.  This would be if each
permutation is transformed from the previous by exchanging the elements of a
single pair of adjacent elements.

A puzzle is a problem whose method of solution is not obvious.  This problem
qualifies for it is certainly not obvious how to solve it. It is also the kind
of problem found in elementary programming textbooks.

The solution here is a function "commuted", which given n and the sequence
number of a permutation, tells which pair, 1..n-1, to exchange to obtain that
permutation from the previous.

For n = 4 and q = 1 to 4! this yields (extra spacing added):

  1 2 3 1   3 2 1 3   1 2 3 1    3 2 1 3   1 2 3 1   3 2 1 3

Starting with 1234 these generate:

  2134 2314 2341 3241   3214 3124 1324 1342   3142 3412 3421 4321
  4312 4132 1432 1423   4123 4213 4231 2431   2413 2143 1243 1234

Forth.

: commuted ( n q -- i)
   DUP 0=
      IF   NIP EXIT   THEN
   0 >R
   BEGIN
      OVER /MOD ( n r q)
      2 PICK 1 > 2 PICK 0= AND
   WHILE   NIP ( n q)
      DUP 1 AND 0=
         IF   R> 1+ >R   THEN
      -1 +under
   REPEAT ( n r q)
   1 AND
   IF ( n r)
      OVER - NEGATE
   THEN   NIP ( r)
   R> + ;

If you need it : +under ( a b c -- a+c b) ROT + SWAP ;

ABC.

HOW TO RETURN n commuted q:
   IF q = 0: RETURN 0
   PUT 0 IN adjust
   PUT floor (q / n), q mod n IN q, r
   WHILE r = 0 AND n > 1:
      IF q mod 2 = 0:
         PUT adjust + 1 IN adjust
      PUT n - 1 IN n
      PUT floor (q / n), q mod n IN q, r
   IF q mod 2 = 1:
      PUT n - r IN r
   RETURN adjust + r

This problem is not an academic exercise.  In the fifties the NSA built
special hardware to do this for cryptoanalys.  It is also useful in the design
of experiments.

Further question: is Forth a suitable language for this kind of problem?

Procedamus in pace. 


del,72
-----
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