Previous page Next page Navigation bar

Programs

Mathematics Programs

Permutations

Summary

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:

Is compatible CFX-9850G

Compatible with CFX-9850G

Is compatible FX-7400G

Compatible with FX-7400G

Other programs
required:

VRPRE, VRSAVFJ, VRRESFJ

Detailed Description

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 alpha-beta search limiting techniques, PERMUTE also provides for a user-written 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.

Usage

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 non-zero 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.

Program Source

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 H-1->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
(F-J+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 ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 19 May 2002.

Brian’s Casio Calculator Corner

Home

Programs

Index

Linkage Conventions

Mathematics

Index

Factorization

Bisection

Newton’s Method

Complex Zeroes

Best Fraction Approximation

Pseudorandom Numbers

Romberg Integration

First Degree ODE

Rounding

Permutations

Finance

Physics

Utility

Tutorial

Puzzles

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data