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