Encontrar la posición de una permutación específica en una lista ordenada alfabéticamente de permutaciones sobre elementos {1,2, ... , k} , k}

Question

Tengo que crear dos algoritmos (pero creo que es más bien una cuestión de combinatoria).

Sea una lista de permutaciones sobre elementos $\{1,2,...,k\}, k \in N$ y esta lista está ordenada alfabéticamente (lo que significa que, por ejemplo, las permutaciones con $\pi(1) = 10$ está en esta lista antes que $\pi(1) = 2$ ).

1) Encontrar la posición de la permutación especificada en esa lista - por ejemplo, la entrada es (1, 2, 4, 3, 5) y encontrar la posición, daría 3

2) Encontrar qué permutación se encuentra en esa lista en la posición especificada - Por ejemplo, la entrada es 3 y debo encontrar qué permutación está en la tercera línea, que puede ser algo como (1, 2, 4, 3, 5)

Intenté enfocar esto como contar las permutaciones que pueden ser antes de la especificada, pero parece bastante complicado ya que $k$ puede ser un número enorme... al menos para mí como novato en combinatoria.

¿Existe tal vez alguna aproximación que me dé algún punto de partida decente desde el que pueda empezar a comprobar permutaciones manualmente y que no tenga una complejidad de tiempo exponencial?

¡Muchas gracias!

Answer 1

No creo que su ejemplo de $14523$ es el tercero. Hay $12345,12354,13245,13254$ y más antes.

Utilizaremos la ordenación lexicográfica, donde los números mantienen su orden habitual. Después de hacer lo que te sugiero, ordena tu lista en orden alfabético y aplica esa permutación a la salida. La clave está en reconocer que hay $(k-1)!$ permutaciones que comienzan con $1$ porque puede pedir el resto de $k-1$ números como quieras. Hay $(k-1)!$ empezando por cada número.

Para 1) si el primer número es $m$ hay $(m-1)(k-1)!$ permutaciones que comienzan con un número menor. Borrar el $m$ de su permutación, reduzca todos los números mayores que $m$ por $1$ y tiene el mismo problema con una permutación de longitud $k-1$ . Llama a esta rutina con esa permutación y añade su resultado a $(m-1)(k-1)!$

Para 2) si $m$ es la posición en la lista el primer número es $\left\lfloor \frac {m-1}{(k-1)!}\right\rfloor +1$ donde el $-1$ y $+1$ vienen porque empezamos a contar en $1$ pas $0$ . De nuevo, quita el primer número y tienes un problema con $k-1$ números, así que llama a la rutina de nuevo.