Superpermutação
# Superpermutação

Em matemática combinatória, uma superpermutação de n símbolos é uma sequência que contém cada permutação de n símbolos como subsequências. Embora seja possível criar superpermutações triviais apenas concatenando todas as permutações possíveis, versões mais curtas podem existir (exceto para o caso trivial de n = 1) porque a sobreposição é permitida. Por exemplo, no caso de n = 2, a superpermutação 1221 contém todas as permutações possíveis (12 e 21), mas a sequência mais curta 121 também abrange ambas.
Foi demonstrado que para 1 ≤ n ≤ 5, a menor superpermutação de n símbolos tem comprimento dado pela soma 1! + 2! + … + n! (sequência A180632 na OEIS). As quatro menores superpermutações conhecidas têm, respectivamente, os comprimentos 1, 3, 9 e 33, formando as sequências 1, 121, 123121321 e 123412314231243121342132413214321. No entanto, para n = 5, existem várias superpermutações menores com comprimento 153. Uma dessas superpermutações é mostrada abaixo, enquanto outra do mesmo comprimento pode ser obtida trocando todos os quatros e cincos na segunda metade da sequência (após o 2 em negrito):
12345123­41523412­53412354­12314523­14253142­35142315­42312453­12435124­31524312­54312134­52134251­34215342­13542132­45132415­32413524­13254132­14532143­52143251­432154321
Para os casos de n > 5, ainda não foi provado qual é a menor superpermutação nem identificado um padrão para encontrá-las. No entanto, foram estabelecidos limites inferiores e superiores para seus comprimentos.

## Encontrando superpermutações

Um dos algoritmos mais comuns para criar uma superpermutação de ordem n é um algoritmo recursivo. Primeiro, a superpermutação de ordem n − 1 é dividida em suas permutações individuais na ordem em que apareceram na superpermutação. Cada uma dessas permutações é então colocada ao lado de uma cópia de si mesmas com um n-ésimo símbolo adicionado entre as duas cópias. Finalmente, cada estrutura resultante é colocada próxima uma da outra e todos os símbolos idênticos adjacentes são mesclados.
Por exemplo, uma superpermutação de ordem 3 pode ser criada a partir de uma com 2 símbolos; começando com a superpermutação 121 e dividindo-a nas permutações 12 e 21, as permutações são copiadas e colocadas como 12312 e 21321. Elas são colocadas juntas para criar 1231221321, e os 2s adjacentes idênticos no meio são mesclados para criar 123121321, que é de fato uma superpermutação de ordem 3. Este algoritmo resulta na superpermutação mais curta possível para todos os n menores ou iguais a 5, mas se torna cada vez mais longo do que o mais curto possível à medida que n aumenta além disso.
Outra maneira de encontrar superpermutações consiste em criar um grafo onde cada permutação é um vértice e cada permutação é conectada por uma aresta. Cada aresta tem um peso associado a ela; o peso é calculado observando quantos caracteres podem ser adicionados ao final de uma permutação (removendo o mesmo número de caracteres do início) para resultar na outra permutação. Por exemplo, a aresta de 123 a 312 tem peso 2 porque 123 + 12 = 12312 = 312. Qualquer caminho hamiltoniano através do grafo criado é uma superpermutação, e o problema de encontrar o caminho com o menor peso se torna uma forma do problema do caixeiro-viajante. A primeira instância de uma superpermutação menor que o comprimento 1! + 2! + … + n! foi encontrado usando uma busca de computador sobre este método por Robin Houston.

### Cotas inferiores ou o problema de Haruhi

Em setembro de 2011, um usuário anônimo no fórum de Ciência e Matemática ("/sci/") do 4chan provou que a menor superpermutação de n símbolos (n ≥ 2) tem pelo menos comprimento n! + (n − 1)! + (n − 2)! + n − 3. Em referência à série de anime japonesa A Melancolia de Haruhi Suzumiya, particularmente o fato de ter sido originalmente transmitida como uma narrativa não linear, o problema foi apresentado como o "o problema de Haruhi": se você quisesse assistir aos 14 episódios da primeira temporada da série em todas as ordens possíveis, qual seria a menor sequência de episódios que você precisaria assistir? A prova para esse limite inferior chegou ao interesse do público em geral em outubro de 2018, depois que o matemático e cientista da computação Robin Houston tuitou sobre o assunto. Em 25 de outubro de 2018, Houston, Jay Pantone e Vince Vatter publicaram uma versão refinada desta prova na On-Line Encyclopedia of Integer Sequences (OEIS). Uma versão publicada desta prova, creditada ao "usuário anônimo do 4chan", aparece em Engen e Vatter (2021).
Especificamente para "o problema de Haruhi" (o caso de 14 símbolos), as cotas inferior e superior atuais são 93 884 313 611 e 93 924 230 411, respectivamente. Isso significa que assistir à série em todas as ordens possíveis levaria cerca de 4,3 milhões de anos.

### Cotas superiores

Em 20 de outubro de 2018, adaptando uma construção de Aaron Williams para construir caminhos hamiltonianos através do grafo de Cayley do grupo simétrico, o autor de ficção científica e matemático Greg Egan criou um algoritmo para produzir superpermutações de comprimento n! + (n − 1)! + (n − 2)! + (n − 3)! + n − 3. Até 2018, essas eram as menores superpermutações conhecidas para n ≥ 7. No entanto, em 1º de fevereiro de 2019, Bogdan Coanda anunciou que havia encontrado uma superpermutação para n = 7 de comprimento 5907, ou (n! + (n − 1)! + (n − 2)! + (n − 3)! + n − 3) − 1, o que era um novo recorde. Em 27 de fevereiro de 2019, usando ideias desenvolvidas por Robin Houston, Egan produziu uma superpermutação para n = 7 de comprimento 5906. Se superpermutações mais curtas semelhantes também existem para valores de n > 7 permanece uma questão em aberto.