user
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 {\displaystyle 0..(n!-1)}}
 to an ordering of all the permutations of the integers 

0..
(
n
−
1
)
{\displaystyle {\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 {\displaystyle n}}
 items without duplicates when the total number of permutations is large. Remember that the total number of permutations of 

n
{\displaystyle {\displaystyle n}}
 items is given by 

n
!
{\displaystyle {\displaystyle n!}}
 which grows large very quickly: A 32 bit integer can only hold 

12
!
{\displaystyle {\displaystyle 12!}}
, a 64 bit integer only 

20
!
{\displaystyle {\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

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

   n
   =
   3
   {\displaystyle {\displaystyle n=3}}
    the two functions are indeed inverses of each other.
4. 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

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

Related tasks

1. Factorial\_base\_numbers\_indexing\_permutations\_of\_a\_collection
assistant
(formerly Perl 6)

It is similar to Haskell, but separate something like inversion vector.
It is easy generate random inversion vector without BigInt.

```
use v6;

sub rank2inv ( $rank, $n = * ) {
    $rank.polymod( 1 ..^ $n );
}

sub inv2rank ( @inv ) {
    [+] @inv Z* [\*] 1, 1, * + 1 ... * 
}

sub inv2perm ( @inv, @items is copy = ^@inv.elems ) {
    my @perm;
    for @inv.reverse -> $i {
        @perm.append: @items.splice: $i, 1;
    }
    @perm;
}

sub perm2inv ( @perm ) {     #not in linear time 
    (
        { @perm[++$ .. *].grep( * < $^cur ).elems } for @perm;  
    ).reverse;
}    
    
for ^6 {
    my @row.push: $^rank;
    for ( *.&rank2inv(3) , &inv2perm, &perm2inv, &inv2rank )  -> &code {
        @row.push: code( @row[*-1] );
    }
    say @row;
}

my $perms =  4;      #100;
my $n     = 12;      #144;

say 'Via BigInt rank';
for ( ( ^([*] 1 .. $n) ).pick($perms) ) {
    say $^rank.&rank2inv($n).&inv2perm; 
};

say 'Via inversion vectors';
for ( { my $i=0;  inv2perm (^++$i).roll xx $n } ... *  ).unique( with => &[eqv] ).[^$perms] {
    .say;
};

say 'Via Raku method pick';
for ( { [(^$n).pick(*)] } ... * ).unique( with => &[eqv] ).head($perms) {
    .say
};

```

Output:

```
[0 (0 0 0) [0 1 2] (0 0 0) 0]
[1 (0 1 0) [0 2 1] (0 1 0) 1]
[2 (0 0 1) [1 0 2] (0 0 1) 2]
[3 (0 1 1) [1 2 0] (0 1 1) 3]
[4 (0 0 2) [2 0 1] (0 0 2) 4]
[5 (0 1 2) [2 1 0] (0 1 2) 5]
Via BigInt rank
[4 3 1 8 6 2 0 7 9 11 5 10]
[0 8 11 4 9 3 7 5 2 6 10 1]
[5 7 9 11 10 6 4 1 2 3 0 8]
[9 11 8 6 3 5 7 2 4 0 1 10]
Via inversion vectors
[9 0 3 1 8 2 4 5 11 7 10 6]
[7 3 1 10 0 6 4 11 2 9 8 5]
[9 8 5 11 1 10 0 7 4 6 2 3]
[10 8 6 5 4 9 0 2 11 7 1 3]
Via Raku method pick
[11 0 7 10 9 4 1 8 6 5 2 3]
[4 5 8 3 2 1 7 9 11 0 10 6]
[11 7 9 4 0 8 10 1 5 2 6 3]
[11 10 0 3 4 6 7 9 8 5 1 2]

```