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


   A. 2 0 1                 NB. return rank of permutation
4
   4 A. i.3                 NB. return permutation of rank 4
2 0 1
   0 1 2 3 4 5 A. i. 3      NB. generate all 6 permutations for 3 items
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
   A. 0 1 2 3 4 5 A. i. 3   NB. ranks of each permuation
0 1 2 3 4 5
   ]ranks=: 4 ? !12         NB. 4 random numbers sampled from integers 0 to 12!
315645285 249293994 432230943 23060830
   ranks A. i.12            NB. 4 random samples of 12 items
 7 10 11  8  4 0  2 3 9 5  6 1
 6  2  8 11 10 0  5 9 7 1  3 4
10  9  1  2  0 3  8 6 7 5 11 4
 0  7  4  6 11 5 10 3 9 8  1 2
   (4 ?@$ !144x) A. i.144   NB. 4 random samples of 144 items
117 36 129  85 128  95 27  14 15 119 45 60  21  98 135 106 18 64 132  97  79  84  35 139 101  75  59 13 141  99 86  40 10 140 23  92 125   6 68  41  69  20  56  12 127 65 142 116  71  54   1   5 121  8  78  73 48 30 80 131 111  57 66 100 138  77 37 124 136...
111 65 136  58  92  46  4  83 20  54 21 10  72 110  56  28 13 18  73 133 105 117  63 126 114  43   5 80  45  88 86 108 11  29  0 129  71 141 59  53 113 137   2 102  95 15  35  74 107  61 134  36  32 19 106 100 55 69 76 142  64  49  9  30  47 123 12  97  42...
 64 76 139 122  37 127 57 143 32 108 46 17 126   9  51  59  1 74  23  89  42 124 132  19  93 137  70 86  14 112 83  91 63  39 73  18  90 120 53 103 140  87  43  55 131 40 142 102 107 111  80  65  61 34  66  75 88 92 13 138  50 117 97  20  44   7 56  94  41...
139 87  98 118 125  65 35 112 10  43 85 66  58 131  36  30 50 11 136 130  71 100  79 142  40  69 101 84 143  33 95  26 18  94 13  68   8   0 47  70 129  48 107  64  93 16  83  39  29  81   6 105  78 92 104  60 15 55  4  14   7  91 86  12  31  46 20 133  53...