Permutations for the HP-41
Overview
1°) Random Permutation Generator
2°) Inverse of a Permutation
3°) Product of 2 Permutations
4°) Signature & Number of Inversions
of a Permutation
5°) Permutation >>> Product of Cycles
6°) Product of Cycles >>> Permutation
7°) Derangements
-The following programs deal with permutations of the set { 1
, 2 , ..... , n }
-Each permutation p is denoted by a list { p(1) p(2) ..............
p(n) }
-For example, { 4 2 1 3 } means that p(1) = 4 p(2) = 2 p(3) = 1 p(4) = 3
-As usual, synthetic registers M N O may be replaced by R00 R01
R02
1°) Random Permutation Generator
-This routine stores a pseudo-random permutation p in a block of contiguous
registers ( Rbb thru Ree ) whose control number is bbb.eee
Data Registers: Only those of the permutation.
Flags: /
Subroutines: /
| 01 LBL "RPG"
02 RCL Y 03 STO M 04 SIGN 05 LBL 00 06 STO IND L 07 ISG X |
08 CLX
09 ISG L 10 GTO 00 11 STO N 12 RDN 13 LBL 01 14 R-D |
15 FRC
16 ENTER^ 17 DSE N 18 RCL N 19 * 20 INT 21 ST+ T |
22 CLX
23 RCL IND Z 24 X<> IND T 25 STO IND Z 26 RDN 27 ISG Y 28 GTO 01 |
29 RCL M
30 CLA 31 END |
( 55 bytes )
| STACK | INPUTS | OUTPUTS |
| Y | bbb.eee | r' |
| X | r | bbb.eee |
bbb.eee = control number
r
= random seed "RPG" also returns
another random seed r' in Y-register if needed for other purposes.
Example:
11.016 ENTER^
1
XEQ "RPG" >>> 11.016
-And we get { R11 ............ R16 } = { 2 6 4
5 1 3 } i-e p is defined by p(1)
= 2 p(2) = 6 p(3) = 4 p(4) = 5 p(5) = 1 p(6)
= 3
2°) Inverse of a Permutation
-"PINV" computes the reciprocal permutation p-1 of
a given permutation p defined by a list in registers Rbb thru Ree.
-The inverse is also determined by a list in registers RBB thru REE
( you have to choose RBB so that the 2 blocks of registers do not overlap
)
Data Registers: Only those of the 2
permutations.
Flags: /
Subroutines: /
| 01 LBL "PINV"
02 1 03 - 04 .1 05 % 06 + |
07 STO M
08 X<>Y 09 STO N 10 INT 11 DSE X 12 LBL 01 |
13 RCL IND N
14 RCL M 15 INT 16 + 17 RCL N 18 INT |
19 RCL Z
20 - 21 STO IND Y 22 E-3 23 ST+ M 24 R^ |
25 ISG N
26 GTO 01 27 RCL M 28 ISG X 29 CLA 30 END |
( 55 bytes )
| STACK | INPUTS | OUTPUTS |
| Y | bbb.eee | / |
| X | BBB | BBB.EEE |
Example: p = { 2 7 4 5 1 6 3 } = { R11 ............... R17 }
-If you choose BBB = 21
11.017 ENTER^
21 XEQ "PINV"
>>>> 21.027 --- Execution time = 4s ---
-And you get p-1 = { R21 ................ R27 } = {
5 1 7 3 4 6 2 }
3°) Product of 2 Permutations
-"POP" computes the product ( i-e the composition ) of 2 permutations
p and q .The product is defined by poq(i) = p[q(i)]
i = 1 , 2 , .... , n
Data Registers: Only those of the 3
permutations.
Flags: /
Subroutines: /
| 01 LBL "POP"
02 STO M 03 STO N 04 X<> Z 05 ENTER^ 06 INT |
07 SIGN
08 ST- L 09 ST- N 10 LBL 01 11 ISG N 12 "" |
13 CLX
14 RCL IND Z 15 LASTX 16 + 17 RDN 18 RCL IND T |
19 STO IND N
20 ISG Y 21 CLX 22 ISG Z 23 GTO 01 24 X<> M |
25 RCL N
26 E3 27 / 28 + 29 CLA 30 END |
( 52 bytes )
| STACK | INPUTS | OUTPUTS |
| Z | bbb.eee(p) | / |
| Y | bbb.eee(q) | / |
| X | BBB | BBB.EEE(poq) |
Example:
p = { 2 7 4 5 1
6 3 } = { R11 ............... R17 }
q = { 3 1 4 2 6
7 5 } = { R21 ............... R27 }
-If you choose BBB = 31
11.017 ENTER^
21.027 ENTER^
31 XEQ "POP"
>>>> 31.037 ( in 4 seconds )
And poq = { R31 ............. R37 } = { 4 2 5 7 6 3 1 } ( for instance, q(4) = 2 , p(2) = 7 whence poq(4) = 7 )
-Likewise, you'll get qop = { 1 5
2 6 3 7 4 }
4°) Signature & Number of Inversions of
a Permutation
-The number of inversions I(p) of a permutation p is the number of pairs
( i , j ) such that i < j and p(i) > p(j)
-The signature of p = sgn(p) = (-1)I(p)
-If sgn(p) = +1 the permutation is even
-If sgn(p) = -1 the permutation is odd
Data Registers: Only those of the permutation.
Flags: /
Subroutines: /
| 01 LBL "SGNP"
02 SIGN 03 CLX 04 LBL 01 05 LASTX |
06 LBL 02
07 RCL IND X 08 RCL IND L 09 X>Y? 10 ISG T |
11 CLX
12 R^ 13 R^ 14 ISG X 15 GTO 02 |
16 X<>Y
17 ISG L 18 GTO 01 19 ENTER^ 20 SIGN |
21 CHS
22 LASTX 23 Y^X 24 END |
( 40 bytes )
| STACK | INPUTS | OUTPUTS |
| Y | / | I(p) |
| X | bbb.eee | sgn(p) |
I(p) is also in L-register
Example1: p = { 2 7 4 5 1 6 3 } = { R21 ............... R27 }
21.027 XEQ "SGNP" >>>> sgn(p) = -1
--- Execution time = 8s ---
RDN I(p) = 11
Example2: p = { 2 8 7 10 4 5 3 1 9 6 } = { R11 ............... R20 }
11.020 XEQ "SGNP" >>>> sgn(p) = +1
--- Execution time = 16s ---
RDN I(p) = 24
5°) Permutation >>> Product of Cycles
-Each permutation p can be decomposed in a product ( composition ) of
disjoint cycles.
-A cycle is usually noted ( a b c .... z ) meaning that
p(a) = b p(b) = c .......... p(z) = a
-In the following routine, the product of cycles is symbolized by a
single list, but the coefficients of 2 consecutive cycles have opposite
signs.
-For example, the product ( 1 3 8 ) ( 6 7 )
( 4 2 5 ) is stored { +1 +3 +8
-6 -7 +4 +2 +5 }
-So, the use of extra registers is avoided.
Data Registers: Only those of the 2
lists.
Flag: F10
Subroutines: /
| 01 LBL "P-CY"
02 STO M 03 STO N 04 X<>Y 05 INT 06 ENTER^ 07 CHS 08 LASTX 09 FRC 10 E3 11 * 12 + 13 1 |
14 ST- N
15 ST- Z 16 + 17 STO O 18 SIGN 19 ENTER^ 20 CF 10 21 LBL 01 22 ISG N 23 "" 24 FS? 10 25 CHS 26 STO IND N |
27 ABS
28 RCL Z 29 + 30 RDN 31 RCL IND T 32 X#Y? 33 GTO 01 34 LBL 02 35 SIGN 36 + 37 RCL N 38 E3 39 / |
40 RCLM
41 + 42 SIGN 43 CLX 44 RCL O 45 X<Y? 46 GTO 04 47 LBL 03 48 CLX 49 RCL IND L 50 X<0? 51 CHS 52 X=Y? |
53 GTO 02
54 ISG L 55 GTO 03 56 RDN 57 ENTER^ 58 FC?C 10 59 SF 10 60 GTO 01 61 LBL 04 62 LASTX 63 CF 10 64 CLA 65 END |
( 100 bytes )
| STACK | INPUTS | OUTPUTS |
| Y | bbb.eee | / |
| X | BBB | BBB.EEE |
Example: p = { 2 8 7 10 4 5 3 1 9 6 } = { R11 ............... R20 }
-If you choose BBB = 21
11.020 ENTER^
21 XEQ
"P-CY" >>>> 21.030
--- Execution time = 16s ---
{ R21 .................. R30 } = { +1 +2 +8 -3 -7 +4 +10 +6 +5 -9 }
-Thus, p = ( 1 2 8 ) ( 3 7 ) ( 4 10 6 5 ) ( 9 ) 9 is a fixed-point
Remark:
-If there is only 1 cycle, all the numbers will be positive, and this
could be ambiguous: Does the list symbolize the cycle or the permutation
itself?
-Replace line 20 ( CF 10 ) by SF 10 , thus the first cycle will be
represented by negative numbers.
-The next program will still work without any modification.
6°) Product of Cycles >>> Permutation
-"CY-P" performs the inverse transformation.
-The product of cycles is to be stored as above.
Data Registers: Only those of the 2
lists.
Flag: F10
Subroutines: /
| 01 LBL "CY-P"
02 1 03 - 04 .1 05 % 06 + 07 STO M 08 INT 09 X<>Y 10 STO N 11 X<>Y |
12 RCL IND Y
13 LBL 01 14 ABS 15 STO O 16 LBL 02 17 E-3 18 ST+ M 19 RDN 20 X<> L 21 RCL Y 22 X<>Y |
23 ABS
24 ST+ Y 25 ISG N 26 X=0? 27 GTO 04 28 X<> L 29 RCL IND N 30 * 31 X<0? 32 GTO 03 33 X<> L |
34 ABS
35 STO IND Y 36 RDN 37 GTO 02 38 LBL 03 39 X<> O 40 STO IND Y 41 RDN 42 CLX 43 RCL IND N 44 GTO 01 |
45 LBL 04
46 RCL Z 47 + 48 RCL O 49 STO IND Y 50 RCL M 51 ISG X 52 CLA 53 END |
( 90 bytes )
| STACK | INPUTS | OUTPUTS |
| Y | bbb.eee | / |
| X | BBB | BBB.EEE |
Example: p = ( 2 8 1 ) ( 9 ) ( 3 7 ) ( 10 6 5 4 )
which is stored { +2 +8 +1 -9 +3 +7 -10 -6 -5 -4 } = { R11 ............... R20 } or { -2 -8 -1 +9 -3 -7 +10 +6 +5 +4 }
-If you choose BBB = 21
11.020 ENTER^
21 XEQ
"CY-P" >>>> 21.030
--- Execution time = 7s ---
{ R21 .................. R30 } = { 2 8
7 10 4 5 3 1 9 6 } = p
7°) Derangements
-A derangement is a permutation with no fixed-point: p(i) # i
for all i = 1 , 2 , .......... , n
-The number d(n) of such derangements may be found by the recursive
formula:
d(1) = 0
d(n) = n d(n-1) + (-1)n
Data Registers: /
Flags: /
Subroutines: /
| 01 LBL "DRG"
02 E3 03 / 04 0 05 LBL 01 06 RCL Y 07 INT 08 * 09 1 10 CHS 11 LASTX 12 Y^X 13 + 14 ISG Y 15 GTO 01 16 END |
( 28 bytes )
| STACK | INPUTS | OUTPUTS |
| X | n > 0 | d(n) |
Example:
1 XEQ "DRG" >>> d(1) = 0
13 R/S
>>> d(13) = 2290792932 --- Execution
time = 6s ---
....... and so on .........
-The first values are:
| n | 1 | 2 | 3 | 4 | 5 | 6 |
| d(n) | 0 | 1 | 2 | 9 | 44 | 265 |
-There is a much faster way to compute d(n) i-e d(n) =
INT [ (n!+1)/e ]
| 01 LBL "DRG"
02 FACT 03 1 04 ST+ Y 05 E^X 06 / 07 INT 08 END |
( 17 bytes )
-But this program gives d(13) = 2290792933 instead of the correct
result: 2290792932
-On the other hand, roundoff errors are smaller for large n-values.
References:
[1] Jean-Michel Ferrard - "Mathez la HP-48G/GX" - D3I Diffusion
- ISBN 2-908791-12-9 ( in French )
[2] N.J.A. Sloane's On-Line Encyclopedia of Integer Sequences:
www.research.att.com/~njas/sequences