A particular ranking of a permutation associates an integer with a particular ordering of all the permutations of a set of distinct items.
For our purposes the ranking will assign integers 



0..
(
n
!
−
1
)


{\displaystyle 0..(n!-1)}

 to an ordering of all the permutations of the integers 



0..
(
n
−
1
)


{\displaystyle 0..(n-1)}

.

For example, the permutations of the digits zero to 3 arranged lexicographically have the following rank:

  PERMUTATION      RANK
  (0, 1, 2, 3) ->  0
  (0, 1, 3, 2) ->  1
  (0, 2, 1, 3) ->  2
  (0, 2, 3, 1) ->  3
  (0, 3, 1, 2) ->  4
  (0, 3, 2, 1) ->  5
  (1, 0, 2, 3) ->  6
  (1, 0, 3, 2) ->  7
  (1, 2, 0, 3) ->  8
  (1, 2, 3, 0) ->  9
  (1, 3, 0, 2) -> 10
  (1, 3, 2, 0) -> 11
  (2, 0, 1, 3) -> 12
  (2, 0, 3, 1) -> 13
  (2, 1, 0, 3) -> 14
  (2, 1, 3, 0) -> 15
  (2, 3, 0, 1) -> 16
  (2, 3, 1, 0) -> 17
  (3, 0, 1, 2) -> 18
  (3, 0, 2, 1) -> 19
  (3, 1, 0, 2) -> 20
  (3, 1, 2, 0) -> 21
  (3, 2, 0, 1) -> 22
  (3, 2, 1, 0) -> 23
Algorithms exist that can generate a rank from a permutation for some particular ordering of permutations, and that can generate the same rank from the given individual permutation (i.e. given a rank of 17 produce (2, 3, 1, 0) in the example above).

One use of such algorithms could be in generating a small, random, sample of permutations of 



n


{\displaystyle n}

 items without duplicates when the total number of permutations is large. Remember that the total number of permutations of 



n


{\displaystyle n}

 items is given by 



n
!


{\displaystyle n!}

 which grows large very quickly: A 32 bit integer can only hold 



12
!


{\displaystyle 12!}

, a 64 bit integer only 



20
!


{\displaystyle 20!}

. It becomes difficult to take the straight-forward approach of generating all permutations then taking a random sample of them.

A question on the Stack Overflow site asked how to generate one million random and indivudual permutations of 144 items.



Task

 Create a function to generate a permutation from a rank.
 Create the inverse function that given the permutation generates its rank.
 Show that for 



n
=
3


{\displaystyle n=3}

 the two functions are indeed inverses of each other.
 Compute and show here 4 random, individual, samples of permutations of 12 objects.


Stretch goal

 State how reasonable it would be to use your program to address the limits of the Stack Overflow question.


References

 Ranking and Unranking Permutations in Linear Time by Myrvold & Ruskey. (Also available via Google here).
 Ranks on the DevData site.
 Another answer on Stack Overflow to a different question that explains its algorithm in detail.


Related tasks

Factorial_base_numbers_indexing_permutations_of_a_collection


' version 31-03-2017
' compile with: fbc -s console
 
' Myrvold and Ruskey
' only for up to 20 elements, 21! > 2^64 -1
Function Factorial(n As Integer) As ULongInt
 
    Dim As ULongInt tmp = 1
 
    For i As ULong = 2 To n
        tmp *= i
    Next
 
    Return tmp
 
End Function
 
Sub unrank1(n As ULong, r As ULongInt , pi() As UByte)
 
    If n > 0 Then
        Swap pi(n -1), pi(r Mod n)
        unrank1(n -1, (r \ n), pi())
    End If
 
End Sub
 
Function rank1(n As ULongInt, pi() As UByte, pi_inv() As UByte) As ULongInt
 
    If n = 1 Then Return 0
 
    Dim As UByte s = pi(n -1)
 
    Swap pi(n -1), pi(pi_inv(n -1))
    Swap pi_inv(s), pi_inv(n -1)
 
    Return (s + n * rank1(n -1, pi(), pi_inv()))
 
End Function
 
Sub unrank2(n As ULong, r As ULongInt, pi() As ubyte)
 
    If n > 0 Then
        Dim As ULongInt fac = Factorial(n - 1)
        Dim As ULongint s = r \ fac
        Swap pi(n -1), pi(s)
        unrank2(n -1, r - s * fac, pi())
    End If
 
End Sub
 
Function rank2(n As ULong, pi() As UByte, pi_inv() As UByte) As ULongInt
 
    If n = 1 Then Return 0
    Dim As UByte s = pi(n -1)
    Swap pi(n -1), pi(pi_inv(n -1))
    Swap pi_inv(s), pi_inv(n -1)
    Return (s * Factorial(n -1) + rank2(n -1, pi(), pi_inv()))
 
End Function
 
' ------=< MAIN >=------
 
Dim As ULongInt i, i1, j, n, n1
Dim As UByte pi(), pi_inv()
Dim As String frmt1, frmt2
Randomize timer
 
n = 3 : n1 = Factorial(n) 
ReDim pi(n -1), pi_inv(n - 1)
frmt1 = " ###"
frmt2 = "##"
 
Print "Rank:     unrank1       rank1"
 
For i = 0 To n1 -1
    For j = 0 To n -1
        pi(j) = j
    Next
    Print Using frmt1 & ": --> "; i;
    unrank1(n, i, pi())
    For j = 0 To n -1
        Print Using frmt2; pi(j);
        pi_inv(pi(j))= j
    Next
 
    Print Using "  -->" & frmt1; rank1(n, pi(), pi_inv())
 
Next
 
n = 12 : n1 = Factorial(n)
ReDim pi(n -1), pi_inv(n - 1)
frmt1 = "###########"
frmt2 = "###"
Print : Print "4 random samples of permutations from 12 objects"
Print "  Rank:                     unrank1                         rank1"
 
For i = 1 To 4
    i1 = Int(Rnd * n1)
    For j = 0 To n -1 : pi(j) = j : Next
    Print Using frmt1 & ": --> "; i1; : unrank1(n, i1, pi())
    For j = 0 To n -1 : Print Using frmt2; pi(j);
    pi_inv(pi(j))= j : Next
    Print Using "  -->" & frmt1; rank1(n, pi(), pi_inv())
Next
 
Print : Print String(69,"-") : Print
Print "Rank:     unrank2       rank2"
 
n = 3 : n1 = Factorial(n) 
ReDim pi(n -1), pi_inv(n - 1)
frmt1 = " ###"
frmt2 = "##"
 
 
For i = 0 To n1 -1
    For j = 0 To n -1
        pi(j) = j
    Next
    Print Using  frmt1 & ": --> "; i;
    unrank2(n, i, pi())
    For j = 0 To n -1
        Print Using frmt2; pi(j);
        pi_inv(pi(j))= j
    Next
 
    Print Using "  -->" & frmt1; rank2(n, pi(), pi_inv())
 
Next
 
n = 12 : n1 = Factorial(n)
ReDim pi(n -1), pi_inv(n - 1)
frmt1 = "###########"
frmt2 = "###"
Print : Print "4 random samples of permutations from 12 objects"
Print "  Rank:                     unrank2                         rank2"
 
For i = 1 To 4
    i1 = Int(Rnd * n1)
    For j = 0 To n -1 : pi(j) = j : Next
    Print Using frmt1 & ": --> "; i1; : unrank2(n, i1, pi())
    For j = 0 To n -1 : Print Using frmt2; pi(j);
    pi_inv(pi(j))= j : Next
    Print Using "  -->" & frmt1; rank2(n, pi(), pi_inv())
Next
 
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End