Programs: 
PERMUTE 

Version: 
2.0, 19 May 2002 

Description: 
This program forms all permutations of m items from a set of n items, and passes these permutations to a subroutine for processing. 

Compatibility: 


Other programs 
Many optimization or enumeration problems can be formulated as a function applied to a permutation of items. For example, the travelling salesman problem seeks to minimize the distance travelled in a trip through a set of locations, where the distance from each location to every other location is known, and all locations are to be visited. Certain production problems can be formulated as needing a set of machine setups, where the expense required to change the machine setup from any given setup to any other setup is known. In such problems, it us useful to have a “permutation engine” to generate permutations.
The PERMUTE program can be used to generate all permutations of a set of items. The set of items to be permuted are represented by integer labels: 1, 2, 3, ..., n. As some problems need only permutations of a given sized subset from a larger population, the PERMUTE program also permits the number of items in a permutation to be limited to a value m less than n. Finally, to permit branch and bound or alphabeta search limiting techniques, PERMUTE also provides for a userwritten subroutine to cause all permutations starting with a given set of items to be skipped. This facility could be applied to a travelling salesman problem, for example, when the length of a path through the first few cities already exceeds the shortest complete path known.
The PERMUTE program is intended to be called by another program, and has no user interface.
The calling program must ensure the VRPRE program is called before the PERMUTE program. The calling program must place the number of items in the set to be permuted into A, and the maximum number of items in a permutation into B. These quantities must be integers greater than 0, with B less than or equal to A, and A less than or equal to 255. No check is made to determine whether these conditions are met: the program will simply malfunction if they are not.
The calling program then invokes the PERMUTE subroutine. The PERMUTE subroutine will destroy the contents of A, B, List 1, and List 2.
The user must supply a program PERMPREF (PERMutation PREFix). This program will be called for every permutation or partial permutation generated. The length of the permutation or partial permutation will be placed into variable A. The permutation or partial permutation will be placed into List 1[1], List 1[2], ..., List 1[A]. The PERMPREF program must determine whether the permutation or partial permutation is to be further processed, and return an indication of this determination in variable B. If PERMPREF sets the variable B to 0, the permutation or partial permutation is not further processed. If PERMPREF sets the variable B to a nonzero value, the permutation or partial permutation is further processed. The PERMPREF program must not modify List 1 or List 2, or the variables F through J.
The user must also supply a program PERMITEM (PERMutation ITEM). This program will be called in the case where a permutation of the desired length has been “approved” by PERMPREF. The length of the permutation will be placed into variable A. The permutation will be placed into List 1[1], List 1[2], ..., List 1[A]. The PERMITEM program must determine whether further permutations are to be found, or whether processing is to halt. If PERMITEM sets the variable B to 0, processing halts. If PERMITEM sets the variable B to 1, further permutations, if any, are generated. The PERMITEM program must not modify List 1 or List 2, or the variables F through J.
After all permutations have been generated, or PERMITEM has set the variable B to 0, the PERMUTE subroutine will return to its caller.
A sample set of program using PERMUTE is provided. These sample programs count the number of times the two subroutines PERMPREF and PERMITEM are called, and compare the actual counts with the expected counts. A more elaborate example of using PERMUTE is the Absolute Triangles puzzle.
The programs are available as a text file with .CAT contents, or may be entered as shown below. A semicolon (“;”) marks the beginning of a comment, and is not to be entered into the calculator. Remember that these programs are copyrighted; see the copyright issues page for limitations on redistribution.
Program PERMUTE (316 bytes):
; Program PERMUTE ; ; Function: ; Generates all permutations of a specified length of a specified ; set of elements. Calls the PERMPREF routine to determine whether a ; partial or full permutation should be further processed. Calls the ; PERMITEM routine to process a full permutation. ; ; Variables: ; A is number of elements to permute [input] ; B is length of permutation [input] ; F is number of elements to permute ; G is length of permutation ; H is index of current element being manipulated ; I is value of current element being manipulated ; List 1 is the current partial permutation ; List 2 is the vector of "value in use" flags ; ; Calling sequence: ; {number of elements}>A ; {length of permutation}>B ; Prog "PERMUTE" ; ; Implicit inputs: ; List 6: the variable save stack ; Z: the stack pointer for the variable save stack ; ; Implicit outputs: ; List 6: the variable save stack ; Z: the stack pointer for the variable save stack ; ; Side effects: ; Calls the PERMPREF routine to determine whether a partial or full ; permutation should be processed. ; Calls the PERMITEM routine to process a full permutation. ; ; Symbols used: ; > is the assignment arrow ; <= is the less than or equal to relational ; >= is the greater than or equal to relational ; <> is the not equal to relational Prog "VRSAVFJ" ; Save variables F through J Int Abs A>F ; Get number of elements into F Int Abs B>G ; Get length into G Seq(0,H,1,G,1)>List 1 ; Initialize List 1 to hold permutation Seq(0,H,1,F,1)>List 2 ; Initialize List 2 to hold value used flags 1>H ; Get current index being manipulated 0>I ; Get current value (0 means none) Do ; Repeat until all permutations are done If I<=0 ; If there is no current value Then 1>I ; then use 1 as the current value Else 0>List 2[I] ; otherwise mark the current value as no longer ; in use I+1>I ; and increment the current value IfEnd ; [End of if there is no current value] While 1 ; Loop finding next available value If I>F ; Test if the value exceeds the maximum Then Break ; If so, quit looking IfEnd ; [End fo test if the value exceeds the max] If List 2[I]=0 ; Test if the value is available Then Break ; If so, quit looking IfEnd ; [End of test if value is available] I+1>I ; Go on to next value WhileEnd ; [End of loop finding next available value] If I>F ; Test if the search went past available values Then H1>H ; If so, try incrementing the previous value If H>=1 ; Test if there is a previous value Then List 1[H]>I ; If so, retrieve it IfEnd ; [End of test if there is a previous value] Else I>List 1[H] ; If search found an available value, use it H>A ; Put the length into A Prog "PERMPREF" ; Call the prefix routine If B<>0 ; Test if the prefix is accepted Then If H=G ; Test if the permutation is full length Then H>A ; If so, put the length into A Prog "PERMITEM" ; Call the permutation routine If B=0 ; Test if processing is to continue Then Break ; If not, break out of loop IfEnd ; [End of test if processing continues] Else 1>List 2[I] ; If not, mark the value in use H+1>H ; Increment the length 0>I ; Just starting that level IfEnd ; [End of if permutation is full length] IfEnd ; [End of prefix is accepted] IfEnd ; [End of if available value] LpWhile H>0 ; [End of loop through all permutations] Prog "VRRESFJ" ; Restore variables
Sample program PERMTEST (144 bytes):
; Program PERMTEST ; ; Function: ; *** SAMPLE *** ; Asks the user for a number of items to permute, and the length of ; permutations to be generated. Calls the PERMUTE program to form ; the permutations. Reports the actual and expected number of calls ; to the PERMPREF and PERMITEM routines. ; ; Variables: ; A and B are used for communication with subroutines ; F is the number of items to permute ; G is the length of the permutations ; H is the expected number of calls to PERMPREF ; I is the expected number of calls to PERMITEM ; K is the actual number of calls to PERMPREF (initialized here, ; updated by PERMPREF, reported here) ; L is the actual number of calls to PERMITEM (initialized here, ; updated by PERMITEM, reported here) ; ; Calling sequence: ; None; main program. ; ; Implicit inputs: ; None. ; ; Implicit outputs: ; List 6: the variable save stack ; Z: the stack pointer for the variable save stack ; ; Side effects: ; The PERMPREF and PERMITEM routines are called. ; ; Symbols used: ; > is the assignment arrow ; _ is the display triangle Prog "VRPRE" ; Set up the variable save stack "Items"?>F ; Get number of items into F "Size"?>G ; Get length of permutation into G 0>K ; Zero actual prefix count 0>L ; Zero actual permutation count F>A ; Put number of items into A G>B ; Put length of permutation into B Prog "PERMUTE" ; Generate the permutations 0>H ; Initialize sum accumulator 1>I ; Initialize multiplier accumulator For 1>J To G ; Loop through levels (FJ+1)I>I ; Figure number of possibilities this level I+H>H ; Add into sum accumulator Next ; [End of loop through levels] "Prefixes" ; Report prefixes: K_ ; Actual H_ ; Expected "Permutations" ; Report permutations: L_ ; Actual I ; Expected
Sample program PERMPREF (26 bytes):
; Program PERMPREF ; ; Function: ; *** SAMPLE *** ; Determines whether a permutation prefix is to be abandoned or ; further processed. ; ; Variables: ; A is the length of the permutation (input) ; B is the "processing should continue" flag (output) ; K is the actual number of calls to PERMPREF (initialized in PERM ; TEST, updated here, reported in PERMTEST) ; ; Calling sequence: ; {length of permutation prefix}>A ; {permutation}>List 1 ; Prog "PREFPREF" ; B>{continue flag} ; ; Implicit inputs: ; K: the actual number of calls to PERMPREF ; List 6: the variable save stack ; Z: the stack pointer for the variable save stack ; ; Implicit outputs: ; K: the actual number of calls to PERMPREF ; List 6: the variable save stack ; Z: the stack pointer for the variable save stack ; ; Side effects: ; None. ; ; Symbols used: ; > is the assignment arrow K+1>K 1>B
Sample program PERMITEM ( bytes):
; Program PERMITEM ; ; Function: ; *** SAMPLE *** ; Handles a permutation. ; ; Variables: ; A is the length of the permutation (input) ; B is the "processing should continue" flag (output) ; L is the actual number of calls to PERMPREF (initialized in PERM ; TEST, updated here, reported in PERMTEST) ; ; Calling sequence: ; {length of permutation}>A ; {permutation}>List 1 ; Prog "PREFITEM" ; B>{continue flag} ; ; Implicit inputs: ; L: the actual number of calls to PERMPREF ; List 6: the variable save stack ; Z: the stack pointer for the variable save stack ; ; Implicit outputs: ; L: the actual number of calls to PERMPREF ; List 6: the variable save stack ; Z: the stack pointer for the variable save stack ; ; Side effects: ; None. ; ; Symbols used: ; > is the assignment arrow L+1>L 1>B
[ Previous page  Top of page  Next page ]
Copyright © 2001 Brian Hetrick
Page last updated 19 May 2002.