Dada una permutación $\pi$ de la primera $n$ números naturales $[1,2,...,n]$ . Necesito encontrar el rango lexicográfico de esta permutación, es decir el $1$ -de esta permutación cuando todos los $n!$ Las permutaciones se escriben en orden lexicográfico. ¿Hay alguna forma rápida de encontrar esto? Gracias por cualquier ayuda.
Respuesta
¿Demasiados anuncios?
Jon Mark Perry
Puntos
4480
Imaginemos $n=5$ y $\pi=[3,4,1,5,2]$ . Dado que $[1,2,3,4,5]$ está en la posición $1$ y $[5,4,3,2,1]$ está en la posición $120$ deseamos encontrar la posición de $\pi$ .
Podemos hacerlo leyendo los dígitos de $\pi$ de izquierda a derecha, y encontrar su relativa valor en el conjunto asociado de dígitos restantes.
La primera es fácil. En este caso tenemos $3$ . Esto significa que la permutación está en el $3^{rd}$ $5-tile$ es decir $pos(\pi)\in[49,72]$ .
Los dígitos restantes son $4,1,5,2$ . La siguiente cifra es $4$ y esto se ordena $3^{rd}$ del conjunto. Esto significa que en nuestra gama de $24$ , se encuentra en el $3^{rd}$ trimestre, por lo que ahora tenemos $pos(\pi)\in[62,67]$ .
A continuación tenemos $1$ que se ordena primero en $1,5,2$ y por lo tanto $pos(\pi)\in[62,63]$ .
$5$ es el siguiente, diciéndonos que $pos(\pi)=63$ .
