thumb|A distribuição de permutações em uma superpermutação de 3 símbolos
Em matemática combinatória, uma superpermutação de símbolos é uma sequência que contém cada permutação de 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 ) porque a sobreposição é permitida. Por exemplo, no caso de , 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 , a menor superpermutação de símbolos tem comprimento dado pela soma . 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 , 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):
123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321
Para os casos de , 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
thumb|Um diagrama da criação de uma superpermutação com 3 símbolos a partir de uma superpermutação com 2 símbolos
Um dos algoritmos mais comuns para criar uma superpermutação de ordem é um algoritmo recursivo. Primeiro, a superpermutação de ordem é 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 -é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 menores ou iguais a 5, mas se torna cada vez mais longo do que o mais curto possível à medida que 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 . 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 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 símbolos () tem pelo menos comprimento . 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 .
Especificamente para "o problema de Haruhi" (o caso de 14 símbolos), as cotas inferior e superior atuais são e , 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 . Até 2018, essas eram as menores superpermutações conhecidas para ≥ 7. No entanto, em 1º de fevereiro de 2019, Bogdan Coanda anunciou que havia encontrado uma superpermutação para = 7 de comprimento 5907, ou , o que era um novo recorde. Em 27 de fevereiro de 2019, usando ideias desenvolvidas por Robin Houston, Egan produziu uma superpermutação para de comprimento 5906. Se superpermutações mais curtas semelhantes também existem para valores de permanece uma questão em aberto.
Leitura adicional
Ligações externas O Problema da Superpermutação Mínima - blog de Nathaniel Johnston
A postagem original do 4chan em /sci/, arquivado no warosu.org Tweet de Robin Houston, que chamou a atenção para a publicação do 4chan Artigo sobre o problema de encontrar superpermutações curtas na Revista Quanta
Categoria:Permutações