• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Guest tsenart

[Resolvido] Programa que mostra todas as variações de uma string

6 mensagens neste tópico

Encontrei este código na net e acho fantástico. Ainda não o consegui perceber muito bem(por cause da recursividade) mas postei para vcs experimentarem!

#include <iostream>
#include <string>

using namespace std;

string switchchars(string topermute, int x, int y)
{
string newstring = topermute;
newstring[x] = newstring[y];
newstring[y] = topermute[x]; //avoids temp variable
return newstring;
}
void permute(string topermute, int place)
{
if(place == topermute.length() - 1)
{
	cout<<topermute<<endl;
}
for(int nextchar = place; nextchar < topermute.length(); nextchar++)
{
	permute(switchchars(topermute, place, nextchar), place+1);
}
}

int main(int argc, char* argv[])
{
if(argc!=2)
{
	cout<<"Proper input is 'permute string'\n";
}
else
{
	permute(argv[1], 0);
}
return 0;
}

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

É uma solução muito boa, mas eu ainda faria alterações....

        // (...)
        if(place == topermute.length() - 1)
        {
	cout<<topermute<<endl;
}
        else
        for(int nextchar = place; nextchar < topermute.length(); nextchar++)
        {
	        permute(switchchars(topermute, place, nextchar), place+1);
        }
        // (...)

o ciclo for ía ser iniciado, mesmo quando place == topermute.length() - 1, mas não ía servir de nada porque ao fixar o último, não ía trocá-lo com ele próprio e ver as permutações dos restantes (que não existem)... Assim chama-se a switchchars menos vezes...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

chama-se recorrência/recursividade.

backtracking é a resolução de um problema por força bruta, tentando todas as possibilidades até que se encontre a solução.

usa-se recorrência em muitas situações.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

backtracking é a resolução de um problema por força bruta, tentando todas as possibilidades até que se encontre a solução.

usa-se recorrência em muitas situações.

Exacto, por isso é que é backtracking. Geras recursivamente todas as combinações de letras, e cada permutação é uma solução para o problema.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora