Para una clase de permutaciones, no podemos esperar clasificar las permutaciones de C con menos de O ( log | C n | ) comparaciones, donde por convención C n : = C ∩ S n .
En particular, cuando está cerrado por subpatrones, se sigue por el teorema de Marcus-Tardos (refinado por J. Fox) que | C n | ≤ C n , donde C es la constante Stanley-Wilf de C . Esto lleva a la siguiente pregunta: ¿es posible clasificar dicha clase utilizando como máximo comparaciones O ( n log C ) ? Esta pregunta es un refuerzo de la pregunta 1 en el documento ' Clasificación rápida y permutaciones para evitar patrones ' de D. Arthur.
Parece posible representar una estrategia de clasificación de este tipo mediante un árbol binario que esencialmente imitaría un algoritmo de clasificación de fusión 'desequilibrado'. Aquí está la idea: dada una permutación , buscaríamos un árbol T π marcado con hojas por los puntos de π , de modo que para cada nodo u de T π la 'superposición' entre los dos subárboles secundarios sería O ( log C ) (en el peor de los casos o en promedio). Sin embargo, sospecho que es necesaria una estructura más involucrada para resolver este problema; Debería admitir una solución positiva.
fuente
Respuestas:
fuente