How to find the index of a k-permutation from n elements?

I know that, for a k-permutation p of size k, built from n elements, there are:

P(n, k) = n! / (n - k)!

possible k-permutations. For example:

k = 2
n = 4
l = [1, 2, 3, 4]
P(n, k) = 4! / (4 - 2)! = 12

1 2 | 2 1 | 3 1 | 4 1
1 3 | 2 3 | 3 2 | 4 2
1 4 | 2 4 | 3 4 | 4 3

And yet another example:

k = 3
n = 4
l = [1, 2, 3, 4]
P(n, k) = 4! / (4 - 3)! = 24

1 2 3 | 2 1 3 | 3 1 2 | 4 1 2
1 2 4 | 2 1 4 | 3 1 4 | 4 1 3
1 3 2 | 2 3 1 | 3 2 1 | 4 2 1
1 3 4 | 2 3 4 | 3 2 4 | 4 2 3
1 4 2 | 2 4 1 | 3 4 1 | 4 3 1
1 4 3 | 2 4 3 | 3 4 2 | 4 3 2

So, how do I find the index of the k-permutation p? Consider the permutations to be generated lexicographically.

Edit: I could start by finding in which "block" p is, addressing the block by the first element of p. For example, for p = [3, 2, 4], the index for p should be at least 12 (counting from 0 to P(n, k) - 1).

But then, to find the second element inside that "block", I'd have to see what are the remaining items to be found, and in which position they will be. I mean, I'd be eventually addressing the list [1, 4], and 4 would be at position 2, so simply using the element as key would require some extra manipulation.

I could use a hash to look up the elements and update their positions, but it'd give me a O(n^2) time complexity. Is it possible to do any better?

The previous version of this answer seemed wrong when I attempted to write code for it. Here is Python code based on the answer, https://math.stackexchange.com/a/4038528/75712

import itertools
import math
import random


def rank(p: list[int], elements: set[int]) -> int:
  """Rank a permutation of k out of n things.

  Args:
    p: The permutation to rank
    elements: The elements to choose from

  Returns:
    The rank of the permutation within all choices of
      k out of n things
  """

  k = len(p)

  if k == 1:
    return len(list(e for e in elements if e < p[0]))

  head, tail = p[0], p[1:]

  n = len(elements) - 1
  num_preceding = len([e for e in elements if e < head])

  preceding = num_preceding * (
      math.factorial(n)
      / math.factorial(n - k + 1)
  )

  return int(preceding) + rank(tail, elements - {head})


def _update_p(p: list[int], i: int) -> None:
  """Update a candidate unranked permutation

  Args:
    p: The permutation to update
    i: The index of the leftmost element to attempt to
      increment

  Returns:
    None
  """

  p[i] += 1
  prev = p[:i]
  while p[i] in prev:
    p[i] += 1
  for j in range(i + 1, len(p)):
    p[j] = 0
    prev = p[:j]
    while p[j] in prev:
      p[j] += 1


def unrank(index, k, n):
  """Unrank a permutation of k out of n things.

  Args:
    index: The rank of the permutation to unrank
    k: The cardinality of the permutation
    n: The size of the set the permutation is chosen
      from, which is enumerated consecutively from zero

  Returns:
    The unranked permutation
  """

  elements = sorted(range(n))
  p = elements[:k]
  for i in range(k):
    if p[i] == n - 1:
      continue
    while True:
      r = rank(p, set(elements))
      if r > index:
        break
      prev = p[:]
      _update_p(p, i)
    p = prev
  return p


# Test rank and unrank by checking reversibility
num_tests = 1
max_n = 800
max_k = 24


for _ in range(num_tests):
  n = random.randint(5, max_n)
  k = random.randint(2, min(max_k, n))

  p = random.sample(range(n), k)
  elements = set(range(n))
  
  rank_p = rank(p, elements)
  unranked = unrank(rank_p, k, n)

  if unranked != p:
    print((p, n, rank_p, unranked, rank(unranked, elements)))
    break

print('Done.')