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: algorithms permutations Baden Message-ID: <12353@sdcc6.ucsd.edu> Date: 21 Aug 90 05:00:06 GMT Organization: University of California, San Diego Lines: 260 EXPRESSING ALGORITHMS Wil Baden raised a general question about the proper domain of Forth. He presented an algorithm for generating permutations and asked whether Forth is a good language for discovering and implementing mathematical algorithms of this sort. In this article, I'd like to present a Forth implementation of an algorithm for the permutation problem -- leaving the discussion of how it was discovered to a sequel. Terminology: For the purposes of this article, a permutation of a set is a rearrangement of its elements. A transposition is a permutation which interchanges two elements. An adjacent transposition interchanges two adjacent elements. If a set has n elements we will sometimes use 1 , ... , n-1 to refer to the adjacent transpositions -- j will be the adjacent transposition that switches the element in position j with the element in position j+1. Problem: Given n, find a sequence of adjacent transpositions which when applied successively generate all permutations. Define a function PERM which depends on n (and also the state of the system) so that each call to PERM generates the next adjacent transposition. Example: If n = 3 then the sequence 1 2 1 2 1 2 generates adj transpo { 1 2 3 } <-- starting arrangement 1 { 2 1 3 } 2 { 2 3 1 } 1 { 3 2 1 } 2 { 3 1 2 } 1 { 1 3 2 } 2 { 1 2 3 } I. A solution to the problem was given as ALGORITHM 115 in the CACM (August 1962) by H. F. Trotter. Wil Baden independently discovered an algorithm generating the same sequence of adjacent transpositions and also converted Trotter's algorithm to Forth. Here is the transcription: 10 CONSTANT Maxperm CREATE P Maxperm ALLOT 1 P C! CREATE D Maxperm ALLOT : perm ( n -- i) P C@ IF 0 DO ( ) 0 P I + C! 1 D I + C! LOOP 0 EXIT THEN 0 ( n k) 1 ROT 1- DO ( k) D I + C@ P I + C+! P I + C@ ( k q) DUP IF DUP I > 0= IF + UNLOOP EXIT THEN DROP ( k) -1 D I + C! ELSE ( k q) DROP ( k) 1 D I + C! 1+ THEN -1 +LOOP 1 P C! 1+ ; If you lack : C+! ( n a -- ) DUP C@ +under C! ; II. Here is an approach (which generates the same sequence) together with the underlying idea: Idea (and proof): Start with {1 2 3 ... n} and apply the adjacent transpositions 1,2,..,n-1. We see that the 1 migrates from left to right without disturbing the order of the other elements: Example: { 1 2 3 } 1 { 2 1 3 } 2 { 2 3 1 } We call this the Ascending sequence. Notice that it generates all possible permutations in which 2..n are in a given order (initially in ascending order). With 1 in the far right position, we apply the next adjacent transposition for n-1 elements to obtain a new arrangement of 2..n. Now we use the Descending sequence n-1,...,1 of transpositions to get 1 back to the left -- notice that, again, the order of the elements 2..n is not changed. Finally we apply the next transposition for n-1 elements (noting that they are shifted one position to the right). The sequence to be generated consists of cycles of length 2n 1 2 3 .. n-1 X n-1 .. 2 1 Y Where X and Y are obtained by a recursive call to the function with n-1 as an argument. We repeat these cycles until all permutations of 2,..,n have been generated and 1 has occupied all positions for each. We use the language construct If( c1 e1 c2 e2 ... ck ek )If Where the ci are non-destructive conditionals (they add a flag to the top of the existing stack). This construct finds the first ci which tests TRUE, executes the corresponding ei and exits the construct. Each ei is responsible for cleaning the stack -- the last conditional is often TRUE to clean the stack if all other conditions fail. The state of the system is given by the position (0 < pos <= 2n) within the cycle. The position must be maintained for each n. Here is the code for the required function: : Perm ( n -- t ) DUP 2 = \ terminal condition IF DROP 1 ELSE DUP Next-Pos ( n pos ) If( ; : Ascending SWAP DROP ; : =n? 2DUP = ; : p(n-1) DROP 1- p ; : <2n? 2DUP SWAP 2* < ; : Descending SWAP 2* SWAP - ; : p(n-1)+1 DROP DUP 0Pos 1- p 1+ ; \ Main function : Perm ( n -- t ) DUP 2 = IF DROP 1 ELSE DUP Next-Pos ( n pos ) If( IF SWAP DROP ELSE 2DUP = IF DROP 1- PERM2 ELSE 2DUP SWAP 2* < IF SWAP 2* SWAP - ELSE DROP DUP 0POS 1- PERM2 1+ THEN THEN THEN THEN ; VERTICAL STYLE A writing style that is becoming popular in Forth (perhaps because of the use of text files rather than blocks) is to write unfactored definitions vertically -- adding copious comments in an effort to compensate for the resulting lack of clarity. I have made an effort to reproduce this style here. Since I don't consider myself adept at this, perhaps someone can show us how to rearrange this code and improve the clarity. : PERM2 ( n -- t ) RECURSIVE DUP 2 = IF DROP 1 \ Terminal ELSE DUP CELLS %Pos + \ get address in position array DUP @ 1+ \ increment position DUP ROT ! \ store new position ( n pos ) 2DUP > IF \ pos < n SWAP DROP ( pos) ELSE 2DUP = IF \ pos = n DROP 1- PERM2 \ recursive call with n-1 ELSE 2DUP SWAP 2* < IF \ pos < 2n SWAP 2* SWAP - \ return t=2n-pos ELSE DROP ( n) DUP 0POS \ set position to 0 1- PERM2 \ recursive call with n-1 1+ \ shift position to right THEN THEN THEN THEN ; Footnote on execution speed: PERM2 is 8% faster than Baden's transcription of Trotter's algorithm. It is 20% faster than the factored version PERM. It is 8 times slower than the 'C' version which Wil supplied in an earlier posting (high level Forth typically runs about 8 times slower than 'C' -- but Forth with selected words coded in assembly language runs faster). Comment on Style: Sometimes the word "efficiency" is used solely in terms of execution speed. Another view of "efficiency" takes into account the programmer's time and the usefulness of the ideas represented in the code. In some areas it is very useful to write code "efficiently" -- in the sense that it can be easily modified, that larger structures can be built from it, and that the ideas can be used by the author and others in future applications. Forth can be written clearly (and efficiently in this sense) but probably not by adopting the stylistic conventions of other languages. I think that Wil Baden's idea of starting some exchanges on the subject of Forth style is excellent. John J Wavrik jjwavrik@ucsd.edu Dept of Math C-012 Univ of Calif - San Diego La Jolla, CA 92093