Permutation numbering system using the factorial base

permnumber.py

"""Permutation numbering system

https://www.numdam.org/item/?id=BSMF_1888__16__176_0
"""

# Author: Vlad Niculae <[email protected]>
# License: MIT

import numpy as np


def _figurative_sign(perm):
    fsign = np.array(perm)  # make a copy
    for i in range(len(perm) - 1):
        mask = fsign[i+1:] > fsign[i]
        fsign[i+1:][mask] -= 1
    return fsign[:-1]


def _factorial_base_to_decimal(fsign):
    n = fsign.shape[0]
    facts = np.cumprod(np.arange(1, n+1))[::-1]
    return np.dot(fsign, facts)


def permutation_rank(perm):
    fsign = _figurative_sign(perm)
    rank = _factorial_base_to_decimal(fsign)
    return rank


def test_permutation_rank():

    from itertools import permutations

    for k, perm in enumerate(permutations(range(5))):
        perm = np.array(perm)
        rank = permutation_rank(perm)
        assert rank == k


if __name__ == '__main__':
    import pytest
    pytest.main([__file__])