2 added 794 characters in body
source | link

The Lehmer code is easily adapted. Instead of using $\binom{n}{k} = \frac{n!}{k! (n-k)!}$, which counts unordered subsets, use $\frac{n!}{(n-k)!}$, which counts ordered subsets.

In Python:

from functools import reduce
from operator import mul


def falling_factorial(n, k):
    return reduce(mul, range(n-k+1, n+1), 1)


def lexicographic_rank(n, perm):
    if len(perm) == 0:
        return 0

    a = perm[0]
    return a * falling_factorial(n - 1, len(perm) - 1) + \
        lexicographic_rank(n - 1, [i if i < a else i - 1 for i in perm[1:]])

Online demo

The Lehmer code is easily adapted. Instead of using $\binom{n}{k} = \frac{n!}{k! (n-k)!}$, which counts unordered subsets, use $\frac{n!}{(n-k)!}$, which counts ordered subsets.

The Lehmer code is easily adapted. Instead of using $\binom{n}{k} = \frac{n!}{k! (n-k)!}$, which counts unordered subsets, use $\frac{n!}{(n-k)!}$, which counts ordered subsets.

In Python:

from functools import reduce
from operator import mul


def falling_factorial(n, k):
    return reduce(mul, range(n-k+1, n+1), 1)


def lexicographic_rank(n, perm):
    if len(perm) == 0:
        return 0

    a = perm[0]
    return a * falling_factorial(n - 1, len(perm) - 1) + \
        lexicographic_rank(n - 1, [i if i < a else i - 1 for i in perm[1:]])

Online demo

1
source | link

The Lehmer code is easily adapted. Instead of using $\binom{n}{k} = \frac{n!}{k! (n-k)!}$, which counts unordered subsets, use $\frac{n!}{(n-k)!}$, which counts ordered subsets.