Estratégias hierárquicas de classificação para permutações para evitar padrões?

8

Para uma classe de permutações, não podemos esperar classificar as permutações de com comparações menores que , onde por convenção .C O ( log | C n | ) C n : = CS nCO(registro|Cn|)Cn: =CSn

Em particular, quando é fechado por subpadrões, segue-se o teorema de Marcus-Tardos (refinado por J. Fox) que onde é a constante de Stanley-Wilf de . Isso leva à seguinte pergunta: é possível classificar essa classe usando no máximo comparações ? Esta questão é um fortalecimento da questão 1 no artigo ' Permutações de classificação rápida e que evitam padrões ' de D. Arthur.| C n | C n CC|Cn|CnC O ( N log C )CO(nregistroC)

Parece possível representar essa estratégia de classificação por uma árvore binária que imitaria essencialmente um algoritmo de classificação de mesclagem 'desequilibrado'. Aqui está a idéia: dada uma permutação , procuraríamos uma árvore T π rotulada pelos pontos de π , de modo que, para cada nó u de T π, a 'sobreposição' entre as duas subárvores filhas fosse O ( log C ) (na pior das hipóteses ou em média). No entanto, suspeito que seja necessária uma estrutura mais envolvida para resolver esse problema; deveria admitir uma solução positiva.πTππvocêTπO(registroC)

NisaiVloot
fonte
2
O que você quer dizer com "fechado por subpadrões"? Isso é diferente de evitar um padrão fixo?
Sasho Nikolov
Pela referência a Stanley-Wilf, parece que é exatamente isso que se pretende.
Suresh Venkat
1
Uma questão relacionada: quando é possível representar uma classe de permutações evitando um padrão em n log C bits? βnregistroC
precisa saber é o seguinte
1
@ShohoNikolov: eu quis dizer fechamento sob a relação de 'envolvimento' como é comumente chamado; isso é equivalente a evitar um conjunto (possivelmente infinito) de padrões.
NisaiVloot
@SureshVenkat: é viável para classes específicas que admitem uma representação baseada em árvore ou em palavra; resolver o caso geral com uma representação de poli-tempo está aberto até onde eu sei. No idioma da enumeração combinatória, esse é um problema de classificação / desclassificação , enquanto o problema de listagem relacionado pode ser feito com eficiência por meio da geração de árvores.
NisaiVloot

Respostas:

2

Outra abordagem é a codificação enumerativa. Considere, por exemplo, evitar permutações, das quais existem C n . O número de 231 -avoiding permutações com π - 1 ( n ) = i é C i - 1 C n - i , e isto dá um algoritmo recursivo para codificar 231 permutações -avoiding: dividir o intervalo de [ 0 , C n ) para n intervalos I 1 , ,231Cn231π-1(n)=EuCEu-1Cn-Eu231[0 0,Cn)n dos comprimentos C i C n - i - 1 para i = 1 , , n arbitrariamente. Dada uma permutação com π - 1 ( n ) = i , observe que π | 1 , , i - 1 é umapermutação 231 que evita { 1 , , i - 1 } e π | EuEu1,,EunCEuCn-Eu-1Eu=1,,nπ-1(n)=Euπ|1,,Eu-1231{1,,Eu-1} é umapermutação231 queevita{i+1,,n}. Recursivamente codificam a primeira parte em[0, C i - 1 )e a segunda parte em[0, C n - i ), e colocou as duas codificações em conjunto para codificarπem eu i .π|Eu+1,,n231{Eu+1,,n}[0 0,CEu-1)[0 0,Cn-Eu)πEuEu

Para qualquer outro , as permutações que evitam τ são bijetivamente relacionadas às permutações que evitam 231 , tomando a inversa, complementando os elementos, revertendo ou a bijeção de Simion-Schmidt entre 132 - e 123 - evitando permutações. Portanto, essa codificação se aplica a todos os padrões de comprimento 3 .τS3τ2311321233

Yuval Filmus
fonte