Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!ucsd!sdcc6!ir230 From: ir230@sdcc6.ucsd.edu (john wavrik) Newsgroups: comp.lang.forth Subject: Domain of Forth Keywords: discovering algorithms Message-ID: <12534@sdcc6.ucsd.edu> Date: 4 Sep 90 03:53:32 GMT Organization: University of California, San Diego Lines: 314 DISCOVERING ALGORITHMS One of the most important features of Forth is that it has properties that make it ideally suited for experimental computing -- and hence for discovering algorithms and proofs of theorems. Some of the reasons that make Forth a good prototyping language also account for its excellence in developing algorithms. Forth is also one of the few languages that allows a great deal of flexibility in the introduction of new data types and operations on them. It is one of the few languages that provide an environment in which algorithms can be modified as easily as data. It is hard to write about the process of discovering algorithms. There are no standard rules or procedures. Sometimes an algorithm is the result of systematic hard work. Sometimes it is a matter of gaining enough experience with the subject matter until it becomes obvious. Mathematics is presented in such a theoretical way that few people outside the subject appreciate the amount of experimentation that goes in to the development of theory. Wil Baden asked about the "Domain of Forth". My claim is that the domain of Forth includes the ability to write tools to help in the discovery of algorithms -- and I'd like to give an example to show why. I can't think of any better way to explain how Forth is useful in discovering algorithms other than to give an illustrated account showing how Forth was used to discover the solution to Wil Baden's permutation problem. ---------- The permutation algorithm was a good test case. Most mathematicians are familiar enough with permutations (as algebraic objects) to work with the problem -- but may, as in my case, be unfamiliar with the combinatorial point of view needed to deal with this particular problem. (Combinatorics is the part of mathematics that deals with counting or listing things; Algebra is the part of mathematics that studies operations on sets). I started this problem fairly ignorant. By the end the solution appeared so simple and clear that it should have been obvious at the start. What was lacking was some experience with this way of looking at permutations. In the old days this experience would have come from working with pencil and paper. Here it came from playing around with a Forth-based permutation system -- a lot faster and more fun. Step 1 - Build a Permutation "Calculator" One of the primary tools for discovering algorithms is a means for gaining experience with the objects under study -- a means for exploring to test promising approaches and to rule out dead ends. The Permutation "Calculator" is such a tool. A permutation of {1 .. n} is, from an algebraic point of view, a mapping of the set {1 .. n} to itself which sends distinct elements to distinct elements. Permutations were represented as arrays. The 0-th element of the array is the size, n. The jth element is the number to which j is sent. Permutations are multiplied by composition: P1 * P2 is the map P1 followed by the map P2. Notation example: { 2 3 1 4 } sends 1->2, 2->3, 3->1, 4->4. The calculator provides: PERMUTATION P ( defining word -- P puts address on stack ) P* ( Perm1 Perm2 -- Perm-product ) P/ PINVERT ( Perm -- Perm-inverse ) P. ( perm -- ) print permutation P= ( Perm1 Perm2 -- flag ) { .. } ( -- perm ) input permutation PMOVE ( Perm1 Perm2 -- ) copy Perm1 to Perm2 Permutations are also represented in terms of their decomposition into cycles. Example: ( 1 2 3 ) sends 1->2, 2->3, 3->1 it permutes 1 2 3 cyclically. C. ( perm -- ) print perm as product of cycles (( .. )) ( -- perm ) input cycle The storage mechanism from JFAR vol 6 # 1 was introduced to allow permutations to be manipulated like integers. A transposition is a cycle which consist of exactly two elements (equivalently, a permutation which exchanges two elements and keeps everything else fixed). Calculator Examples: 1. { 1 2 4 3 } { 4 3 2 1 } p* p. { 4 3 1 2 } The first permutation sends 1->1, 2->2, 3->4, 4->3 The second sends 1->4, 2->3, 3->2, 4->1 So the product (first followed by second) sends 1->4, 2->3, 3->1, 4->2 Notice that { 2 3 1 4 } puts this permutation on the stack (what is actually on the stack is the address where the data is stored). P* multiplies the top two elements and the stack and puts the result on the stack. P. prints the permutation on top of the stack. 2. { 2 3 1 4 } dup pinvert p. { 3 1 2 4 } 3. { 2 1 4 3 } c. (1 2 )(3 4 ) 4. (( 1 2 3 )) p. { 2 3 1 4 } As is typical for Forth-based mathematical systems, the basic permutation system was extended in a "middle out" fashion. The initial system provided the basic algebra of permutations (and I/O). New features were added and old features refined as the need arose. Step 2. Examine sequences of permutations At this point Baden's problem became mixed with other problems involving sequences of polynomials. One is to produce permutations in lexicographic order. To study this, we put the permutations into lexicographic order (as an array) and then printed the permutations and the quotients needed to get from one permutation to the next. (If you can spot the pattern in the quotients, you will be able to write the algorithm for generating the permutations lexicographically.) : QUOTS CR #P 1- 0 DO I P P. ( print perm ) I 1+ P I P P/ 14 SPACES C. ( print quot indented ) LOOP #P 1- P P. ; load-3 quots { 1 2 3 } (2 3 ) { 1 3 2 } (1 3 2 ) { 2 1 3 } (2 3 ) { 2 3 1 } (1 2 3 ) { 3 1 2 } (2 3 ) { 3 2 1 } load-4 quots { 1 2 3 4 } (3 4 ) { 1 2 4 3 } (2 4 3 ) { 1 3 2 4 } (3 4 ) { 1 3 4 2 } (2 3 4 ) { 1 4 2 3 } (3 4 ) { 1 4 3 2 } (1 4 2 ) { 2 1 3 4 } (3 4 ) { 2 1 4 3 } (2 4 3 ) { 2 3 1 4 } (3 4 ) { 2 3 4 1 } (2 3 4 ) { 2 4 1 3 } (3 4 ) { 2 4 3 1 } (1 3 )(2 4 ) { 3 1 2 4 } (3 4 ) { 3 1 4 2 } (2 4 3 ) { 3 2 1 4 } (3 4 ) { 3 2 4 1 } (2 3 4 ) { 3 4 1 2 } (3 4 ) { 3 4 2 1 } (1 2 4 ) { 4 1 2 3 } (3 4 ) { 4 1 3 2 } (2 4 3 ) { 4 2 1 3 } (3 4 ) { 4 2 3 1 } (2 3 4 ) { 4 3 1 2 } (3 4 ) { 4 3 2 1 } To facilitate further exploration the permutations for n=3,4,5,6 were generated as virtual arrays. [Converting an in-memory array to a disk array involves a minor change in a defining word.] Step 3. Use a backtracking algorithm to find all solutions to Baden's problem for n=3 and n=4. Look for nice patterns. For n=3 there are only two adjacent transpositions ( 1 2 ) and ( 2 3 ) we abbreviate these 1 and 2 [see earlier posting]. There are exactly two solutions to Baden's problem: 1 2 1 2 1 2 and 2 1 2 1 2 1 Where 1 2 1 2 1 2 means: start with { 1 2 3 } exchange the first two elements, then the second two, repeat three times. [In this case it is obvious that there can only be two possible chains of adjacent transpositions -- but it is not obvious that they generate all permutations.] We experimented at this point with some possible generalizations to n=4. None of them worked (in particular 1 2 3 1 2 3 1 2 3 ... is *not* the pattern for n=4. For n=4 there are 344 chains of adjacent transpositions that generate all permutations (i.e. 344 solutions to Baden's problem). These were found by using a backtracking algorithm implemented with the permutation calculator of step 1. The problem is to explore a tree. At the root of the tree is the permutation { 1 2 3 }. There are branches to the three permutations (nodes) that can be obtained by applying the three possible adjacent transpositions. The same is true at every node (except that one transposition leads back to the previous node). The algorithm explores the tree and prints every path which generates all permutations. soln 1: 1 2 1 2 1 3 1 2 1 2 1 3 1 2 3 2 1 2 1 2 3 2 1 soln 43: 1 2 3 1 3 2 1 3 1 2 3 1 3 2 1 3 1 2 3 1 3 2 1 soln 62: 1 2 3 2 3 2 1 2 1 2 3 2 3 2 1 2 1 2 3 2 3 2 1 Looking for patterns is a very human mathematical activity. It is not at all obvious what we (as humans) look for when we look for "nice" patterns. It would be a very interesting problem in artifical intelligence to instruct a computer to scan a collection of sequences like this and pick out those which seem most "useful". In particular, the computer should see #62 as 1 2 3 2 3 2 1 2 repeated and #43 as 1 2 3 1 3 2 1 3 repeated [#43 and #62 were the "nicest" patterns found by eye] --------------------------- NOTE: At this point there was enough information to solve Baden's problem. If only we had stopped to see what these sequences of transpositions do to the permutations (as we did later), the algorithm (and its proof) would have been clear. But the study was taken a step further: --------------------------- Step 4. Look at permutations from a combinatorial point of view Let Xn be the set of (a1,..,an) with 0 <= ai <= n-i There are n! elements in Xn. I had a telephone conversation with Wil Baden which informed me that he (and probably Trotter) considered permutations as associated with elements of Xn. I subsequently looked at the book "Combinatorics for Computer Science" by S. Gill Williamson Computer Science Press ISBN 0-88175-020-4 As it turns out, there are a variety of correspondences between the set Xn and the set of permutations of {1,..,n}. None of these seem to have anything to do with the algebraic structure of permutations -- but they do have something to do with listing the permutations in various orders. The permutation calculator was extended to include include some of these correspondences. In particular we defined >B and >W to use Baden's and one of Williamson's methods for obtaining an element of Xn from a permutation, and B> and W> for the inverse maps. We also implemented a RANK function on the symbols in Xn. Williamson gives a "method of adjacent marks" which produces a correspondence between symbols in Xn and permutations. If the symbols in Xn are arranged in lexicographic order, the corresponding permutations are obtained from one another by adjacent transpositions. This provides another (but more complicated) algorithm for solving Wil Baden's problem. ================================================================== CONCLUSION ================================================================== What was done here is not easy to do in most languages: we were able to easily build what amounts to a special language for studying permutations -- and then use the language to develop an algorithm. An important application area for Forth is experimental computing in mathematics. It's usefulness comes from its ability to support the definition of new data types and language features -- allowing the mathematician to make a laboratory to perform experiments. Forth is a good language for making mathematical laboratories. John J Wavrik jjwavrik@ucsd.edu Dept of Math C-012 Univ of Calif - San Diego La Jolla, CA 92093