Permutando Strings

[Matheus Brandão]

Pessoal, alguém aqui conhece algum algoritmo que permute elementos de uma string alfanumérica e consiga enumerar essas permutações de forma que quando eu necessite utilizar certa permutação eu apenas passe ao programa um número decimal e acesse instantaneamente aquela permutação?

Estou perguntando isso porque escrevi um algoritmo capaz disso. Vou dar um exemplo: suponhamos que você deseja permutar uma string de 4 elementos , sabe-se que teremos 4! ou seja 24 possibilidades de permutações, os algoritmos que testei da internet permutaram apenas números e fazem do seguinte modo: eles pegam os valores 0, 1, 2 ,3 e criam uma lista de 0000 a 3333 e vão peneirando o que seria uma permutação válida ou seja, sequencias em que não há repetição de elementos, por exemplo: 1123 ou 2232, deixando apenas valores como 3210 ou 0231. Isso faz com que o custo computacional aumente muito porque ele vai gerar vários valores desnecessários e testa-los, até em uma linguagem como python que tem suporte a números gigantes quando tento calcular uma permutação com 10 elementos o computador trava, já com meu algoritmo eu gero somente as permutações necessárias e ainda resolvo outro problema que é o de como enumerar essas permutações.

Suponhamos que queremos permutar uma string alfanumérica de 20 elementos por exemplo eu tenho 20! que dão 2432902008176640000 permutações, se eu quiser a permutação de numero 43290200817664000 basta eu digitar esse numero decimal no meu código e ele me devolve a permutação que está nessa ordem instantaneamente. Esse é o pulo do gato do algoritmo que foi projetado pelo meu irmão e escrito por mim em C.

Enquanto pesquiso em grupos se existe alguém que fez algo parecido e se há alguma aplicação para esse algoritmo, um membro de um grupo de programação me disse que existe um algoritmo no qual em gero permutações com até 100 elementos ou mais, esse algoritmo é o Steinhaus–Johnson–Trotter, ele é mais eficiente porque gera permutações sem ter que peneirar valores inválidos como eu disse anteriormente mas, ele ainda não foi capaz de enumerar as permutações e acessa-las instantaneamente como o meu, o Steinhaus–Johnson–Trotter assim como o meu para gerar todas as  permutações com 100 elementos demora uma eternidade em máquinas convencionais atuais, mas como falei anteriormente o meu algoritmo tem um diferencial, eu tenho de antemão nele uma função matemática que me da acesso a qualquer ordem da permutação, bastando apenas eu digitar o número decimal válido dentro do range de 0 até (n! - 1) que estou permutando, eu também posso reverter  a permutação para a string original sabendo até quantos swaps foram realizados para retornar a string original.

O algoritmo Steinhaus–Johnson–Trotter além de gerar permutações apenas com números (meu algoritmo permuta valores alfanuméricos) ele não é capaz de enumerar e acessar em tempo real as permutação como o meu, ele primeiro tem que gerar todas as permutações (o que com 100 elementos já se torna impossível) e após gerar as permutações ele vai acessar através de uma array usando um método a permutação desejada.

Enfim galera, conhecem algum algoritmo capaz de fazer isso? Ou sabe onde pode ser aplicado? Sei que ele seria ótimo para criptografia e um cara me disse em uma página que para calcular cross overs na área de genética ele seria muito útil, essas são áreas muito específicas, eu gostaria de saber de alguém antes se já conhecem algum algoritmo que faz isso ou se esse algoritmo desenvolvido por meu irmão é algo totalmente novo.

Desde já agradeço a atenção.

[Fernando Mercês]

Que legal, Matheus! Eu não conheço um algoritmo com este recurso. O mais próximo que conheço sobre permutações é o crunch, que suporta permutação mas a ideia é gerar listas de senhas. Espero que alguém que entenda sobre algoritmos possa te ajudar por aqui.

Grande abraço!

[maycon]

Olá Matheus,

Existem algoritmos para geração de permutação baseados em heap sem esse critério de ter que varrer toda sequência e validar o que faz parte da permutação ou não. O próprio Python possui essa implementação no itertools.permutation(), além do próprio std::next_permutation() da STL do C++.

Com relação a geração da enézima (nth) permutação, também é possível encontrar algumas soluções para isso. Um exemplo pode ser visto aqui. Para outras soluções basta procurar por "nth/kth permutation algorithm" ou similar.

Uma boa referência para se aprofundar nisso é o TAOCP Vol. 3 do Knuth. Lá você terá uma referência sólida e bem matemática sobre esses assuntos.

Att,
Maycon Vitali