Fwd: re: Puzzler: Permutations and Anagrams 
Author Message
 Fwd: re: Puzzler: Permutations and Anagrams

This message apparently was not received by some members of the list.

Eugene McDonnell
---------------------
Forwarded message:
Subj:    re: Puzzler: Permutations and Anagrams
Date:    95-12-07 22:19:24 EST
From:    Eemcd


Jim Weigang's comments on algorithms for generating the i-th lexical
permutation of {iota} N reminds me of some ancient APL history, largely
because Weigang's function LEXPERM1 to do this is almost identical to the
function PERM by L. J. Woodrum that appeared in "APL\360 User's Manual", IBM
T. J. Watson Research Center, July, 1968.

Luther Woodrum was a largely self-taught programmer with special expertise in
the art of sorting whom I first met at the IBM Kingston plant in 1964 or 5,
and who later moved to IBM's Poughkeepsie plant. I believe he became aware of
Iverson notation while at the IBM Systems Research Institute in New York
City, near UN Plaza. At any rate, when the implementation that was to become
APL began in May of 1966, he volunteered to help. He suggested to the group
that APL could use a grading primitive, and begged to be allowed to implement
it, using his own design. He was told he could only do so if he could find
the space to do this by reducing the size of other code in the interpreter.
This was because APL\360 was running on an IBM Model 50 with 256K of memory,
supporting 20 concurrent users with 36K workspaces, and space was at a
premium. Somehow or other he managed to do this by slimming down or
eliminating various pieces of code (one of the things he got rid of was
monadic base value, which yielded the boolean vector form of an integer). He
put the code in, which dismayed Phil Abrams, who thought the grades were mere
data processing forms, not really intrinsic to the nature of APL. However,
soon after they were available it was found that they had wondrous
mathematical properties, for example that four upgrades of a permutation
vector was an identity operation.

I had always thought that Luther's PERM function was based on the work of D.
H. Lehmer (born 1905), not his father D. N. Lehmer (1867-1938), I first read
about it, at any rate, in an article by D. H. written in the 1950's. There,
Lehmer described the 'factorial digits' number system, in which numbers were
represented in the base with successively larger digits, right to left. The
particular use they have is, as Weigang points out, to permit easy conversion
between the lexical number of a permutation and the permutation itself. In my
"At Play With J" column in the July 1995 issue (vol. 12 no. 1) of the British
APL magazine Vector (pp 125-128) I describe a seies of functions for
converting between the standard form, reduced form, and atomic (=lexical)
form of a permutation. The tables below show the forms for permutations of
length 3:

 standard reduced atomic
   0 1 2   0 0 0    0
   0 2 1   0 1 0    1
   1 0 2   1 0 0    2
   1 2 0   1 1 0    3
   2 0 1   2 0 0    4
   2 1 0   2 1 0    5

Since it is quite easy to convert between reduced and atomic forms (using
base value and representation with factorial digits base) the real interest
is in converting between standard and reduced forms.

Here are two functions for converting between the reduced and the standard
representations of a permutation. For example, the reduced form r =. 2 0 1 0
will be converted by the function sfr to the standard form d=. 2 0 3 1; and d
will be converted to r by the function rfs.



The idea behind sfr is, beginning at the right, to add 1 to each element to
the right of a given element which is greater than or equal to the element.
The "ranking" function (double upgrade) is used to do this. It replaces the
cumbersome use of the greater than or equal relational form on line 7 of
Weigang's LEXPERM1. To see how this works, you can execute the expression:

   /:^:(2) 2 , /:^:(2) 0 , /:^:(2) 1 , 0

The idea behind rfs is, for each element, to replace it by the sum of the
number of elements to its right that it is greater than. To see how this
works, you can execute the expression:

   (+/2>0 3 1) , (+/0>3 1) , (+/3>1) , (+/1>'')

The suffix adverb (\.) in J was proposed precisely because it was needed in
rfs, but, as so often happens, it finds many other uses..

These conversions are also discussed by Ken Iverson in his "Notation as a
Tool of Thought", CACM 23, August 1980, also reprinted in "A Source Book of
APL", APL Press, 1981, pp 105-128, see functions DFR and RFD, discussed on p.
117, column 2.

Eugene McDonnell



Wed, 27 May 1998 03:00:00 GMT  
 
 [ 1 post ] 

 Relevant Pages 

1. Puzzler: Permutations and Anagrams

2. Puzzler: Permutations and Anagrams

3. Puzzler: Permutations and Anagrams

4. Puzzler: function of permutation vector

5. all-permutations is faster than permutation

6. A permutation on permutations

7. Anagram Assist and TopDown vs. BottomUp

8. anagram

9. speedup of anagram finder

10. speedup of anagram finder

11. Anagrams in Prolog

12. Anagram

 

 
Powered by phpBB® Forum Software