# Source code for tryalgo.permutation_rank

```#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Permutation rank

christoph dürr - 2016-2019
"""

# pylint: disable=line-too-long

[docs]
def permutation_rank(p):
"""Given a permutation of {0,..,n-1} find its rank according to
lexicographical order

:param p: list of length n containing all integers from 0 to n-1
:returns: rank between 0 and n! -1
:beware: computation with big numbers
:complexity: `O(n^2)`
"""
n = len(p)
fact = 1                                # compute (n-1) factorial
for i in range(2, n):
fact *= i
r = 0                                   # compute rank of p
digits = list(range(n))                 # all yet unused digits
for i in range(n-1):                    # for all digits except last one
q = digits.index(p[i])
r += fact * q
del digits[q]                       # remove this digit p[i]
fact //= (n - 1 - i)                # weight of next digit
return r

[docs]
def rank_permutation(r, n):
"""Given r and n find the permutation of {0,..,n-1} with rank according to
lexicographical order equal to r

:param r n: integers with 0 ≤ r < n!
:returns: permutation p as a list of n integers
:beware: computation with big numbers
:complexity: `O(n^2)`
"""
fact = 1                               # compute (n-1) factorial
for i in range(2, n):
fact *= i
digits = list(range(n))                # all yet unused digits
p = []                                 # build permutation
for i in range(n):
q = r // fact                      # by decomposing r = q * fact + rest
r %= fact
p.append(digits[q])
del digits[q]                      # remove digit at position q
if i != n - 1:
fact //= (n - 1 - i)           # weight of next digit
return p

```