Permutations

# 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

( 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:

  Jean-Michel Ferrard - "Mathez la HP-48G/GX" - D3I Diffusion - ISBN 2-908791-12-9  ( in French )
  N.J.A. Sloane's On-Line Encyclopedia of Integer Sequences:    www.research.att.com/~njas/sequences