You are here

Evolution of a Computer Application - Permutations

Author(s): 
John J. Wavrik

This package provides the basic representation and manipulation of permutations.  It also provides a procedure for computing the group generated by a given set of permutations.

  1. Overview
  2. Top Level Words and Examples
  3. The Temporary Storage Problem
  4. Cycle Notation
  5. Details
  6. Temporary Storage
  7. Permutation Groups
  8. Bugs, Error Traps, Etc.
  9. Range Checking

a. Overview

A permutation is represented as an array of bytes.  If P is a permutation of 1...n, byte 0 is used to store n and bytes 1...n store P(1)...P(n).   A permutation is represented on the stack by the base address of this block of memory. 

Access words are provided to manipulate permutations:

If P sends i to j,  then  i P Sends  returns j.  To make P send i to k, do k i P Send!.

(The order is chosen to be consistent with Forth "k addr !" to store k at addr.)

In the earliest version of this package, I used a defining word to declare a permutation and set aside storage for it. I provided words for input, output, and multiplication of permutations.  Eventually I added a mechanism to deal with the storage of intermediate results to allow permutations to be used in chain computations.  I also added a procedure to find the group generated by a set of permutations.

b. Top Level Words and Examples

We start with the earliest attempt. Notice that not all of these words are in the current version of Groups32. We make a defining word MakePerm that allocates a block of storage for a named permutation.  We will access the storage as an array of bytes.  If the permutation is understood to permute 1, … , n, we store n in byte 0.  In general, byte k will contain the image of k under the permutation.  The word PInit ( n perm ) initializes a permutation to be the identity.  The word P. ( perm ) prints a permutation.  To store a permutation, I introduced the word P! with stack diagram ( x1 .. xn n perm ), where xk is the image of k under the permutation. An initial version of a multiplication word, here called oP* ( perm1 perm2 - result ), multiplies two permutations and puts the product in a named permutation called Result.


Reminder:  Code in red is found in the early 1990 version, Groups16; Code in green is found in the current Groups32; Blue is used to represent code that was not in the early version and did not survive to Groups32.


Here is how this looks in use:

 

    MakePerm P1  \  Declare P1 and P2
    MakePerm P2  \  as permutations
    1 2 4 3 4 P1 P!  \ Store data
    2 3 4 1 4 P2 P!
    P1 P. {  1 2 4 3 }  \ print permutations
    P2 P. {  2 3 4 1 }
    P1 P2 oP* P. {  2 3 1 4 } 
       \ use default left->right

 

We eventually add input and output in cycle notation, but the most serious problem at the moment is that the definition of multiplication puts all products in the same place: a permutation named Result.  The problem can be seen in this example

    1 2 4 3 4 P1 P!
    2 3 4 1 4 P2 P!
    P1 P2 oP* DUP oP* P. {  3 1 3 4 }

The correct answer is

    P1 P2 P* DUP P* P. {  3 1 2 4 }

What is happening is that the first product P1 P2 oP* is stored as the permutation Result. The sequence DUP oP* makes Result both the input and output.  Since oP* alters the permutation Result, it is altering its input argument in this case.  The conclusion is that for chain calculations there must be more than one place for results.

It is important to understand that this is not a problem peculiar to permutations -- it arises even for integer arithmetic. The stack provides the kind of flexible storage needed. If we perform  a*b + c*d  (using algebraic notation) we would do a b * c d * +  (using reverse Polish notation).  The result of the first multiplication must be temporarily stored until we perform the second multiplication.  The stack diagrams for this sequence of operations show a*b remaining on the stack until the final addition.

c. The Temporary Storage Problem

There are several possibilities for dealing with the problem of intermediate storage. The first, and worst, is to try to put the data for a permutation on the Forth parameter stack. This approach would make a permutation occupy several stack cells. It has the effect of burying useful data and inhibiting the use of the standard stack operations.

A second, more promising, approach is to create a special permutation stack.  Since the same problem of intermediate storage arises with other types of algebraic objects, and since a system might have several types of objects, this would require the user to introduce a new set of stack operations for each stack, and to be aware of the contents of several stacks while programming. This approach is psychologically burdensome.

In Groups32 and other algebra systems I have produced, I have represented objects on the regular Forth stack by an address.  The address occupies a single cell -- so it is manipulated by the usual stack operations.  The user can think of a permutation being on the stack.  SWAP can be used to exchange two objects: two permutations, a permutation and an integer, etc. Thus, representing an object by its address allows a consistent way to integrate new types of data into the system. However, we still need to have a pool of locations for intermediate results.

An improved multiplication word, P*, will remove two (addresses of) permutations from the stack and multiply them. It will then put the result in the next available temporary storage location and return the address of this location to the stack.

In some languages, a very large pool of temporary locations is available -- and computation proceeds, using these locations, until the pool is exhausted.  The system then attempts to identify storage locations that are no longer in active use. Unreferenced locations are called "garbage" and the process of reclaiming them is called "garbage collection". There can be a noticeable pause in execution while the system collects garbage.

We use a mechanism with storage for just 16 temporary objects. It does a very small, quick garbage collection when these are exhausted. Each type of object has its own pool of 16 storage locations. A mechanism is provided for marking an address as available. When a computation is performed on a certain type of object, the result is placed in the next available storage location, and the address is returned to the stack. If no location is available, the system tries to find which locations are no longer in active use.

d. Cycle Notation

The output word C. uses the same naïve algorithm that one uses for computing products by hand. We keep track of which numbers have already been output. Start with all numbers unmarked, and mark any element that is sent to itself. Then start with the first unmarked element. Print an opening parenthesis, print (and mark) the elements in its orbit, and print a closing parenthesis.

The input word (which I have called Perm:) reads from the rest of the command line. It is based on a word that reads a cycle (numbers between two parentheses), and it multiplies the cycles it obtains. The cycles are not required to be disjoint. Perm: does check the syntax -- so it reports errors such as improperly matched parentheses.

    Perm:  (1 2) (1 3)
    C. (1 2 3 )
    Perm: (( 1 2) (1 3
        Syntax Error -- Try Again
    ? (1 2)(1 3)
    C. (1 2 3 )

 

e. Details

33 CONSTANT PMaxSize \ largest n for permutations +1 for count 
: MakePERM   CREATE  PmaxSize ALLOT ;
: 'Element  ( i perm -- addr )  +  ;
: Send!  ( k i perm --   )  
'Element C!  ;
: Sends  ( i perm -- perm[i] ) 
'Element C@ ;
: Degree ( perm -- n ) 
0 SWAP Sends;
: Degree! ( n perm -- )  
0 SWAP Send!   ;
: PInit  ( n perm -- ) 
     2DUP 0 SWAP Send!  SWAP 1+ 1
     ?DO   I DUP 2 PICK Send!   LOOP
     DROP ;
: P.  ( perm -- )
     \ print showing images of 1..n
      ." {  " DUP Degree 1+ 1
      DO  I OVER Sends .  LOOP 
      DROP  ." }"  CR ;
: P!  ( x1 .. xn n perm  -- )  
      2DUP Degree!
      1 ROT DO  I OVER
                >R SWAP Send! R>
        -1 +LOOP DROP ;
DEFER Direction
 MakePERM Result
: oP*  ( perm1 perm2 -- result )
   Direction
   DUP Degree
   DUP  Result Degree!   1+ 1
   DO ( perm2 perm1 )
    I 2 PICK  Sends  ( perm2 perm1 perm2[I] )
    OVER Sends  ( perm2 perm1 perm1[perm2[I]] )
    I Result Send!
   LOOP   2DROP  Result  ;
: Left->Right ['] NOOP IS Direction ;
: Right->Left ['] SWAP IS Direction ;
  Left->Right      \ default

Recall that the multiplication operation defined here puts the product in a fixed permutation called Result and returns the address of that location to the stack.  This code allows for the fact that some books use left to right multiplication while others use right to left.  Forth allows for "vectored execution" using the word DEFER.  The line "DEFER Direction" makes a dictionary entry for Direction, which can then be used in subsequent code.  An action for Direction must be filled in before it is used.  The code is written so that multiplication would be left to right without Direction (so we fill in the action NOOP when this is the desired direction).  If multiplication from right to left is desired, the action for Direction is SWAP.  The words Left->Right and Right->Left allow the direction to be switched without recompiling.

f. Temporary Storage

The user must understand that these temporary locations are a scratchpad area for operations on the objects - any result of lasting use must be moved to a permanent location. The garbage collector assumes that an address is being actively used if and only if it is on the stack. The internal workings of the temporary storage module are transparent to the user.  In the following table I show how the mechanism is introduced into the permutations package.

Temp-Storage Perm-Temps
Establish a new Temp-Storage structure called Perm-Temps.
CREATE  Perm-Storage
    PMaxSize CELLS 16 *
    ALLOT
Make a block of memory to store 16 permutations.
: Perm-Setup 
   Perm-Storage Perm-Temps
   16 0 DO  DUP I Address !
          PMaxSize CELLS +
        LOOP  DROP ;
Initialize Perm-Temps to contain the 16 addresses in the storage pool.
Perm-Setup
Execute the setup.
: PTemp   ( -- perm )
     Perm-Temps  Temp  ;
This is the main word that the user employs - it returns the address for the next available slot in the storage pool.

With this storage mechanism, it is very easy to fix P* without drastically changing the code.  We need only to supply RESULT with the address of the next available location in the storage pool.  Notice that RESULT may be used in several places in the code for an operation, and we do not want to use a different storage location at each reference.  We therefore make RESULT a VALUE (rather than a permutation). It will return the address of the storage area for a permutation. We define a word GetRes to store the address of the next temporary storage slot in RESULT.

0 VALUE Result

: GetRes  PTemp TO Result ;
: P*  ( perm1 perm2 -- result )
  Direction
  GetRes DUP Degree
  DUP  Result Degree!   1+ 1
  DO ( perm2 perm1 )
    I 2 PICK Sends ( perm2 perm1 perm2[I])
    OVER Sends
       ( perm2 perm1 perm1[perm2[I]] )
       I Result Send!
  LOOP   2DROP  Result  ;

 

g. Permutation Groups

The main remaining interesting feature of the permutations package is the ability to find the group generated by a given set of permutations. The algorithm for doing this is to maintain an array of the generating permutations (Gtable) and an array of permutations generated (Ptable). We use the ordered list module, discussed previously, to make the latter array an ordered list.  Start with just the identity permutation in the Ptable. Repeatedly multiply all elements in the Ptable by the generators -- adding any permutation to the Ptable that is not already there.  Continue doing this until a pass (multiplying by generators) does not produce anything new.

The following example shows how this feature is used from the command line. I should mention that I eventually equip Groups32 with a user interface that makes it easier and quicker to use.

\  Klein's 4-group
4 Size! \ This initializes the tables
Gen: (1 2)         \  add the generators
Gen: (3 4)
Make-Group    \ apply the algorithm
Show-Table     \ a multiplication table can be obtained
A  B  C  D

B  A  D  C

C  D  A  B

D  C  B  A
Show-Elements          
Group is of order 4
     A  ()    B  (3 4 )   C  (1 2 )
     D   (1 2 )(3 4 )

At the moment, the permutations package seems disjoint from the rest of Groups32.  We cannot immediately apply any of the procedures for orders, subgroups, etc.  We can, however, generate a table.  We now provide a mechanism for installing this table into the Groups32 system -- replacing any of the tables 1-5 (which are for very small groups and will hardly be missed).

: Install0      \ Install as table 0
        GSize @ Gord!
        GSize @ 0
        DO  GSize @ 0
            DO  J I PG* J I G*! LOOP
        LOOP ;

If the order of the generated permutation group is between 1 and 32, we automatically have the table stored as table 0. (The slot for group #0 is used for temporary storage.)

Groups32 provides the word Install ( n -- ), which will move the table from slot 0 to replace table n, where n is 1, 2, 3, 4, or 5. Once a table is installed, all the commands can be applied to it.

Assume the Klein 4 group is generated as above.

Install0     \ move the current permgroup to slot
1 Install    \ install as group 1
1 Table      \ show the table
_A_B_C_D_

A |A B C D

B |B A D C

C |C D A B

D |D C B A
1 Subgroups   \ show the subgroups
* = Normal subgroup
      Generators            Subgroup
     0  { }                 *{ A }
     1  { B }               *{ A B }
     2  { C }               *{ A C }
     3  { D }               *{ A D }
     4  { B C }             *{ A B C D }

Since Show-Elements provides a concordance of letters A, B, C, … with permutations, it is easy to interpret any results in terms of permutations.

h. Bugs, Error Traps, Etc.

This is an appropriate place to discuss these issues, since I eventually equipped the permutations package with error handling at the point when I first made it available for use by others. I added the error trapping even before I equipped the system with the user interface that I discuss in the next section. The permutation package was not part of the original Groups16 -- it was developed separately and eventually merged into the group theory package.

When a system of this type is used by the person who wrote and implemented it, it is usually possible to minimize "bugs" that arise from coding errors (or from disagreements between the programmer and computer about how the world works). Let us call these "bugs of the first kind". Forth style emphasizes writing short, uncomplicated definitions. Words can be tested interactively as soon as they are written. It can be quickly determined if a word does not function as intended, and the mistake is usually quickly pinpointed.

When a piece of software is used by others, however, another type of bug can appear: improper behavior resulting from incorrect use of the system. We will call these "bugs of the second kind". (Some call these "features".)

A perfect example of a "bug of the second kind" occurs in the earliest version of Groups16. Recall the definition of G*:

: 'ELE   ( ele1 ele2 - addr )    \ compute address      of product
       ID - SWAP ID - GORD * +   \ offset from base address
       GBLK BLOCK GOFFS +        \ address of start of table
       + ;                       \ address of element
: G*  ( ele1 ele2 - ele1*ele2 )  
      'ELE C@  ;

(ID is a constant, 65, the ASCII code of upper case A.)  Group elements are represented in this version by upper case letters. The code assumes that the elements are entered as ASCII codes of upper case letters -- within the range of the particular group.

 

4 Table
 ________
A |A B C D
B |B A D C
C |C D A B
D |D C B A
: Try GETE GETE G* ." = " EMIT ;
Try B C = D
Try b c = A
Try E F = C

When we put in B and C as uppercase, we get the correct answer. This word, however, is case sensitive. When we put in b and c as lowercase, we do not get the correct answer.  We also get an answer when we put in E and F, even though they do not represent letters in the range of this group.

There is no "bug of the first kind" in the definition of G*.  When G* is supplied with valid input it does provide the correct output.  However, the code for G* contains some assumptions about how it is to be used -- and it contains no error traps to ensure it is used correctly. The errors seen here arise because G* was used incorrectly. This is a "bug of the second kind".

When the author is the user, he or she knows the intended form of input. It can be difficult for the author to anticipate some of the things other users might do -- or how the software will respond. In the user interface (Page 10), I have tried to restrict "free form" input so that Groups32 can be used correctly by those unfamiliar with the system. The input for most commands is prompted, and it is easy to test if the input is of the proper type. For example, if the user must enter the number of a group, it is easy to check that the input is a number between 1 and 144. If the user is to put in group elements, it is easy to check whether they are valid. (We automatically convert to upper case -- making the input case insensitive -- but we do check for range.) These are cases where it is rather simple and quick to insure valid input. Many bugs of the second kind can be eliminated by prompting for input in a restricted form and rejecting invalid input.

In some cases, however, we want users to provide input as a line of text -- an example is the word Perm: in the permutations package.  This word is supposed to be supplied with a string that represents a collection of cycles in the numbers 1...n, where n has been specified in advance.

Left->Right
3 TO PSize
Perm: (1 2)(1 3)
C. (1 2 3 )

Here is an early version of code for Perm:  (the names of support words have been changed to correspond to the current ones).

: 'Element  ( i perm -- addr )  +   ;
: Send! ( k i perm -- )   'Element C! ;
: Sends ( i perm -- perm[i] )
          'Element C@ ;
: Degree  ( perm -- n )  0 SWAP Sends  ;
: Degree! ( n perm -- )   0 SWAP Send!   ;
: PInit  ( n perm -- )  2DUP 0 SWAP Send!
      SWAP 1+ 1
   DO   I DUP 2 PICK Send!   LOOP  DROP ;
VARIABLE SvDepth    0 VALUE Result
: GetRes  PTemp TO Result ;
: P*  ( perm1 perm2 -- result ) 
     GetRes DUP Degree
     DUP  Result Degree!   1+ 1
     DO  I 2 PICK  Sends   OVER Sends
         I Result Send!
     LOOP   2DROP  Result  ;
5 VALUE PSize
: <<  GetRes  PSize Result PInit
              DEPTH SvDepth !  ;
: >>  DUP >R  DEPTH SvDepth @ - 1
      DO  OVER Result Send!  LOOP
      R>  Result Send!  Result  ;
: Perm:
\ use single parentheses in following string
     PTemp PSize OVER PInit
     BEGIN   << 
             ASCII ( PARSE 2DROP
             ASCII ) PARSE EVALUATE
             DEPTH SvDepth @ -  WHILE
         >>  P*                 REPEAT ;

The size of a permutation (the n in Sn) is assumed to be in the VALUE PSize. The words << and >> are used for input of a single cycle.  Here is what happens when we type << 1 2 3 >>:

The word << saves the current depth of the stack and initializes a new temporary permutation (called Result).  The numbers 1 2 3 are just put on the stack. The word >> compares the stored stack depth to the new stack depth, thus determining how many numbers are on the stack.  A copy of the top number on the stack is saved on the return stack and a loop is entered that makes each number the image (under the permutation) of the number below it:  2 goes to 3, 1 goes to 2.  The loop is completed by making 3 go to 1.  This is how a cycle is handled.

The word Perm: reads the input that follows it (presumably containing one or more cycles). It uses the <<  .. >> pair to interpret each cycle, and it multiplies the cycles it receives. Perm: ends its work when the input line is exhausted.

This code functions correctly as described -- as long as the user understands the assumptions built into Perm:

  1. There must be a space between Perm: and the rest of the input line.
  2. Perm: must be followed on the input line by a collection of cycles.
  3. There must not be anything else on the input line.
  4. Each cycle must begin with an opening parenthesis "(" and terminated with a closing parenthesis ")".
  5. Within each cycle there must be numbers in the range 1...n.
  6. PSize must be set to n before Perm: is used.
  7. The numbers within a cycle must be separated by spaces.
  8. The numbers within a cycle must be distinct.
  9. No characters, other than digits and spaces, can occur between the parentheses.

Now, what happens if a user supplies Perm: with illegal input?  Suppose the user does not close parentheses, does not match parentheses, or puts illegal characters within parentheses?  The system could react in several ways, ranging from aborting the command to producing something that is not a permutation, and that is handled improperly by P*, C., and other words in the package.

In the first example above, with G*, invalid input produced incorrect answers because numbers are fetched from the wrong part of memory. No damage is caused, just incorrect results. Some words, however, store things in memory, and it is possible that incorrect input could actually alter the code in memory. When Perm: is executed, the word Send! is ultimately called.  This word has the stack diagram ( k i perm -- ).  It will store k in the memory position of index i in the given permutation. If i is not in the proper range, a number will be stored in memory other than within the allocated space for the permutation. If k is not within range, the result will not be a valid permutation, and subsequent operations may lead to numbers being stored in improper places. Since Forth implementations usually allocate data storage within the dictionary, it could turn out that numbers can be erroneously stored in places being used by code -- and the code will, therefore, stop operating correctly.

This should not be taken as an indication of fragility.  In most cases, words that store things receive their arguments from other words that produce only valid input for them.

The final versions of Perm: and its auxiliary words enforce the requirements for a correctly formed input string. The input string is checked for balanced parentheses and for only digits within the parentheses. A range-checked version of Send! is used to make sure the numbers in a cycle are within range and that they are distinct.  Within the command completion interface (see Page 10), Perm: is used in a prompted input sequence, so the user must specify n first. (The word that stores n also checks that it is within range.) All of this is necessary just to try to eliminate bugs of the second kind.

i. Range Checking

Any operation that stores data in memory could, if given erroneous input, store data in unintended places.  To guard against this, one can add range checking to words that store data.  Here is an example from code we have already examined.

In the word Orders there is a word +Ocnt that increments the number in a certain slot in an array. Here is the original version:

CREATE OCNT 33 CELLS ALLOT
: 'OCNT  ( k - addr )  CELLS OCNT +  ;
: +OCNT  ( k --  )   'OCNT  1 SWAP +!  ;

Notice that k must be in the range 0-32 for this to work correctly.  Now here is a version that checks that k is in range:

CREATE OCNT 33 CELLS ALLOT
: 'OCNT  ( k - addr )  CELLS OCNT +  ;
: +OCNT  ( k --  )
    DUP 0 32 BETWEEN NOT
    IF     CR . ." Out of Range " ABORT
    ELSE  'OCNT  1 SWAP +!  THEN ;

There is, of course, a speed penalty for this extra checking.  The original +OCNT executes 100,000 times in 26 milliseconds, while the range-checked version takes 50 milliseconds. The ranged checked version is twice as slow.

Should range-checking be included?

Range checking is obviously not necessary if a word is supplied its parameters only by other words that are guaranteed to supply valid parameters.  +OCNT is a perfect example. This is a word that should NOT include range checking.

To see this, we need to look at how  +OCNT is used. +OCNT occurs in the code for Orders, which calculates the orders of elements for one of the existing groups (of order 1-32). Thus, in use, the word +OCNT cannot receive an out-of-range index.  If we were to use the range-checked version, the number k would be checked each time to see if it is between 0 and 32, but the test will always be true because +OCNT will never receive a k that does not satisfy this condition.

One of the virtues of producing software for your own use is that it is not so necessary to deal with bugs of the second kind (and with error trapping). It can be very time-consuming to prepare a piece of software for use by others. Those who have lived with toddlers will appreciate that it is very much like "child proofing" a house. How much you have to do depends both on the complexity of your house and the sophistication of your toddler. Rather than put all your possessions in locked cabinets, however, you must give thought to what precautions are really most effective.

The critical words to consider for range checking (or other error trapping) are words such as Perm: that get input from the user and store things in memory. These are the words that have the potential to alter the code itself. In the final version of the permutations package, I not only use a range-checked version of Send! but I also include other tests to make sure that the input string has the correct form.

At the beginning of the preceding section, we used the example of G*. It would not be efficient to put range checking into a word like this, which is used very frequently. It would be better to examine the code that passes information to such words, making sure that G* will not receive invalid input. Once the internal code of the system is correct, the only source of invalid data will be input routines. This is usually the best place to put error traps. Since data entry is slow anyhow, error traps here will not significantly slow the system. Once we are sure that the input routines will not send incorrect data to the rest of the system, it should not be necessary to have error traps on lower level words.

John J. Wavrik, "Evolution of a Computer Application - Permutations," Convergence (December 2004)