(48/49/50) Rank of Permutation

[John Keith]

Note: The first program, PRNK, had a bug which would cause the returned value to be larger than the correct value. It has been replaced by a shorter and faster program. Please replace any copies of the old program with the new one.

These two programs compute the rank (lexicographic index) of a permutation, or return a permutation (as a list) given the rank. The rank assumes 1-based lists, i.e. a sorted list has the rank 1. For the HP-48, the maximum length of the permutation list is 14. For the 49 and 50, the length is limited only by memory if used in Exact mode.

The first program, PRNK, takes a list on level 1 and returns the rank as an integer. The program uses LSORT. The built-in SORT command on the 48G and later can be used but it is much slower. For HP48, remove the R\->I commands in line 5.

Code:


\<< 1 SWAP DUP SIZE \-> n
  \<< 1. n 1. -
    FOR j DUP j n SUB DUP LSORT
      SWAP HEAD NEWOB POS 1. - DUP
      { R\->I n j - R\->I ! * ROT + SWAP }
      :: DROP IFTE
    NEXT DROP
  \>>
\>>

The next program, PURNK (permutation unrank) is the inverse of the program above. Given integers n on level 2 and j on level 1, returns a permutation of the numbers 1..n with rank j.

The HP 49/50 version requires ListExt and should be used in exact mode.

Code:


\<< 1 - \-> n j                    @ Assume 1-based list
  \<< n LSEQ 1 n 1 -               @ Start with list of 1..n
    FOR k j n k - ! IDIV2 'j' STO  @ Find next element
      1 + DUP2 GET UNROT LRMOV     @ Remove element from list and save it
    NEXT EVAL n \->LIST            @ Assemble permutation list
  \>>
\>>

The HP-48 version is longer but still reasonably fast. It uses the program 'REL' from One-Minute Marvels as a replacement for LRMOV.

Code:


\<< 1 - \-> n j
  \<< 1 n
    FOR m m
    NEXT n \->LIST 1 n 1 -
    FOR k j n k - !
      DUP2 / FLOOR ROT ROT MOD 'j' STO
      1 + DUP2 GET ROT ROT SWAP LIST\-> 2 +
      DUP ROLL OVER SWAP - ROLL DROP 3 - \->LIST
    NEXT 1 GET n \->LIST
  \>>
\>>

[John Keith]

This is a variation of PURNK that takes a sorted list on level 2 instead of an integer. The objects in the list may be of any type(s).

For instance, with the list { "apple" "banana" "cherry" "grape" } on level 2 and the number 8 on level 1,
the program returns { "banana" "apple" "grape" "cherry" }.

HP 49/50 version:

Code:


\<< 1 - OVER SIZE R\->I \-> j n                 @ n is size of list
  \<< 1 n 1 -
    FOR k j n k - ! IDIV2 'j' STO
      1 + DUP2 GET UNROT LRMOV
    NEXT EVAL n \->LIST
  \>>
\>>

HP-48 version:

Code:


\<< 1 - OVER SIZE \-> j n                        @ n is size of list
  \<< 1 n 1 -
    FOR k j n k - !
      DUP2 / FLOOR ROT ROT MOD 'j' STO
      1 + DUP2 GET SWAP ROT LIST\-> 2 +
      DUP ROLL OVER SWAP - ROLL DROP 3 - \->LIST
    NEXT 1 GET n \->LIST
  \>>
\>>

[John Keith]

The first program in post #1, PRNK, had a bug which caused it to return an incorrect value. The new program is correct as well as being shorter and faster. Please replace any copies of the old program.