Entendendo o problema das permutações anagramáticas
Trabalhar com mesmas letras formando palavras diferentes é mais simples do que muitos programadores imaginam, mas tem uma armadilha clássica que quase todo mundo leva uns dias para perceber. A base do problema é pura matemática combinatória. Se você tem uma palavra de cinco letras, o total de permutações possíveis é 5! (cinco fatorial), que dá 120 combinações. Com seis letras sobe para 720. Com oito letras já estamos em 40.320. Com doze, são 479 milhões de permutações. O crescimento não é linear, é exponencial, e isso é o que quebra a maioria dos scripts quando alguém tenta gerar tudo de uma vez.
Técnica prática para mesmas letras formando palavras diferentes
O caminho mais eficiente para resolver isso sem gastar memória à toa é usar recursão com troca de caracteres. Você percorre a palavra posição por posição, fixa um caractere na posição atual e recursivamente permuta o resto. Quando a profundidade da recursão atinge o tamanho da string, você guarda ou processa a permutação. Isso evita gerar listas intermediárias gigantes e mantém o consumo de memória proporcional apenas à profundidade da recursão, que em palavras de até quinze letras é praticamente irrelevante. Aqui está um exemplo em Python que funciona bem para palavras de até dez letras:
def permutar(s, inicio=None, resultado=None):
if inicio is None:
inicio = 0
if resultado is None:
resultado = []
if inicio == len(s):
resultado.append(''.join(s))
return resultado
for i in range(inicio, len(s)):
s[inicio], s[i] = s[i], s[inicio]
permutar(s, inicio + 1, resultado)
s[inicio], s[i] = s[i], s[inicio]
return resultado O detalhe que muitos ignoram na implementação acima é a troca de volta. Sem restaurar a string após a chamada recursiva, você acaba alterando a ordem original e gera combinações duplicadas ou inválidas, especialmente quando a palavra contém letras repetidas como em "BANANA" ou "CASA".
O problema que ninguém conta sobre repetições
Quando a palavra tem letras repetidas, o número real de permutações únicas cai drasticamente. Para "BANANA", por exemplo, há 6! = 720 permutações brutas, mas dividindo pelos fatoriais das repetições — 3! para os A's e 2! para os N's — sobram apenas 60 anagramas únicos. Se você não tratar isso desde o início, vai processar 660 strings inúteis a mais, o que significa tempo de CPU jogado fora e uso de memória desnecessário ao armazenar resultados que vão ser descartados depois. Uma solução direta é usar conjuntos (sets) para filtrar duplicatas, mas isso não resolve o gasto computacional da geração em si. O jeito mais limpo é aplicar um algoritmo de permutação lexicográfica que pule naturalmente as repetições. A biblioteca itertools.permutations do Python é prática, mas retorna todas as permutações com repetição. Para filtrar de verdade, o ideal é converter o resultado para um set e depois listar, o que para palavras de até oito letras com poucas repetições não costuma ser um gargalo significativo.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Um caso real que aprendi na prática
No passado, precisei validar anagramas para um sistema de crossword automatizado que processe palavras de até doze letras contra um dicionário de cerca de duzentas mil entradas. O primeiro implemente o gerador ingênuo e ele simplesmente travava a máquina porque a pilha de recursão crescia demais e o GC do interpretador entrava em loop constante. A solução foi mudar para um enfoque baseado em tuplas ordenadas de frequências de caracteres — ou seja, em vez de gerar todas as permutações, eu criava uma assinatura única para cada palavra: contagem de cada letra em ordem alfabética. Assim, "amor" e "roma" tinham a mesma assinatura e podiam ser agrupados sem precisar comparar string por string. Esse método reduziu o tempo de processamento de uma validação completa de cerca de trinta minutos para aproximadamente doze segundos em hardware padrão da época.
Limitações e quando essa abordagem falha
Não adianta fingir que permutações são a solução para tudo. Se o seu objetivo é encontrar anagramas em um corpus grande — como verificar se duas frases inteiras são anagramas uma da outra — a abordagem de gerar todas as permutações não escala. Ela funciona bem para palavras curtas, de até oito ou nove letras, mas a partir daí o custo computacional explode. Nesse cenário, a técnica de assinatura por frequência de caracteres é muito mais indicada, pois tem complexidade O(n) em vez de O(n!). Outro ponto fraco é a questão dos acentos e caracteres especiais. Em português, "café" e "cafe" são visualmente diferentes, mas algoritmos que não normalizam o texto tratam 'é' e 'e' como caracteres distintos, gerando falsos negativos. A solução é normalizar a string usando unicodedata.nfc do Python ou similar em outras linguagens, antes de calcular as assinaturas ou gerar permutações. Sem essa etapa, seu sistema vai ignorar anagramas válidos sem motivo.
Se você precisa de uma solução pronta e leve para uso geral, uma boa alternativa é a função anagramas de bibliotecas como anagrama ou ana em Python, que já encapsulam a normalização de acentos e a filtragem de duplicatas. Para projetos maiores, considere usar bancos de dados com índices por assinatura de anagrama, que permitem consultas em tempo constante independente do tamanho da palavra.
Conclusão prática
O segredo para trabalhar com mesmas letras formando palavras diferentes não está na geração em si, mas em escolher a estratégia certa para o tamanho do problema. Palavras curtas com pouca repetição — gere permutações com recursão. Palavras longas ou com muitas repetições — use assinatura de frequência. E nunca esqueça de normalizar acentos, senão seu sistema vai perder anagramas legítimos e você vai gastar horas caçando bugs que na verdade são apenas um problema de Unicode mal tratado.
