¿Estrategias de clasificación jerárquica para permutaciones que evitan patrones?

8

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 : = CS n .CCO(log|Cn|)Cn:=CSn

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.C|Cn|CnCCO(nlogC)

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.πTππuTπO(logC)

NisaiVloot
fuente
2
¿Qué quieres decir con "cerrado por subpatterns"? ¿Es esto algo diferente de evitar un patrón fijo?
Sasho Nikolov
Por la referencia a Stanley-Wilf, parece que esto es exactamente lo que se pretende.
Suresh Venkat
1
βnlogC
1
@SashoNikolov: quise decir cierre bajo la relación de 'participación' como comúnmente se le llama; Esto es equivalente a evitar un conjunto (posiblemente infinito) de patrones.
NisaiVloot
@SureshVenkat: es factible para clases específicas que admiten una representación basada en árboles o palabras; resolver el caso general con una representación poli-tiempo está abierto hasta donde yo sé. En el lenguaje de la enumeración combinatoria, este es un problema de clasificación / descalificación , mientras que el problema de listado relacionado se puede hacer de manera eficiente mediante la generación de árboles.
NisaiVloot

Respuestas:

2

231Cn231π1(n)=iCi1Cni231[0,Cn)nI1,,InCiCni1i=1,,nπ1(n)=iπ|1,,i1231{1,,i1}π|i+1,,n231{i+1,,n}[0,Ci1)[0,Cni)πIi

τS3τ2311321233

Yuval Filmus
fuente