Mudar posição de letras

[Kingflare]

Olá pessoal, boa tarde! Tudo bem? Então, estava aqui pensando em uma maneira de trocar posição de letras de uma palavra a fim de permutá-la. Por exemplo, vamos supor a palavra " CAI", permutando as letras teríamos:

CAI

IAC

AIC

CIA

ACI

ICA

Como eu poderia implementar algo desse tipo em ppascal? Como fazer com que o programa não repita permutações? Desde já agradeço!

[thoga31]

Uma forma mais intuitiva de fazer isso é de forma recursiva. Se organizares as permutações, vais ter isto:

-> CAI
  CIA
-> ACI
  AIC
-> IAC
  ICA

Ou seja, pegas numa letra do conjunto e aplicas a função de permutação às seguintes, e no final concatenas esses resultados com a letra.

Por exemplo:

CAI -> C + [AI]

Aplicar Permutação([AI]): [AI, IA]
Concatenar C com resultados:
  C + AI  =  CAI
  C + IA  =  CIA

Isto vai criar permutações repetidas, pelo que, no final, fazes uma "limpeza" através de uma função que elimine duplicados.

Agora coloca-se o desafio: criar a função que cria as permutações. 🙂

Percebeste o conceito que te introduzi?

Experimenta com papel e caneta para treinar o raciocínio acerca desta função.

Edited March 14, 2015 at 07:43 PM by thoga31

[Kingflare]

Olá, toga! Tudo bem? Então, ainda estou pensando a cerca do programa e tenho feito assim:

program project;

uses crt,sysutils;

var
 sequencia:string;
 a,fat:integer;

procedure permutarString(s:string);

var
 j:integer;

procedure permutar(seq:string; posi:integer);

var
   selecionado,semselecao,inicio,final,anagrama:string;
   i:integer;

  begin
    selecionado:=Copy(seq,posi,1);// copia da sequencia a partir da posição 1, somente 1 elemento, como a entrada foi 123, o valor que a variável recebe é 1
    semselecao:=Copy(seq,1,posi-1) + Copy(seq,posi+1,length(seq)); //Copia a partir da posição 1, a posição-1(que no caso será 0) sendo assim não copiará
                                                                                                            // valor + A partir da posição+1 copia os elementos, na string a partir da posição 2
                                                                                                          // que todos os elementos serão copiados, assim a variável recebe 23

for i:= 0 to length(semselecao) do     //loop para montar nova string

   begin
       inicio:=Copy(semselecao,0,I);                                   // a partir da posição 0, copiar i elementos, no primeiro loop, copiará nenhum elemento assim, inicio recebe ''
       final:=Copy(semselecao,i+1,length(semselecao));  // a partir da posição i+1 copia o resto da string, assim, copiará a partir 1 todos os lementos, variável final recebe 23
       anagrama:= inicio+selecionado+final;                    // monta a string variável inicio é vazia + variável selecionado=1 +variável final (23)
                                                                                     //assim, anagrama terá valor final 123, formando o primeiro anagrama
   end;

       if nao_repetido(anagrama) then // nao repetido é uma função que estou inventando, caso o elemento não seja repetido, ela retorna verdadeiro e entra no loop
         begin
         writeln(anagrama);
         permutarstring(anagrama);// chama o procedimento para permutar a string
         end;
end;

begin
  for j:= 1 to length(s) do //inicia o loop
   permutar(s,j); //faz a chamada ao procedimento permutar
end;


begin
 writeln('Digite um sequencia');
 read(sequencia);//entradade de dados, vamos supor que a entrada seja 123
 permutarString(sequencia); //chamada do procedimento que recebe a string a fim de permutá-la
 readkey;
end.

Então inicialmente, antes de montar a função que elimina elementos repetidos montei esse código, com o intuito de saber se ele está montando as permutando corretamente. Contudo, quando faço a chamada recursiva do procedimento "permutarstring(anagrama)" o programa entra em loop infinito e eu não consegui entender o porque, tens como me explicar?

Para a função(parte onde há elementos repetidos), eu estava pensando no seguinte, iria criar um vetor no qual eu jogaria as palavras nele de acordo com a minha função. Por exemplo, o programa montou a palavra CBA, então eu chamaria a função e percorreria o vetor, caso o valor não estivesse lá, colocaria a Palavra dentro do vetor.

Mas por enquanto, quero só conseguir pelo menos montar a permutação. Desde já, agradeço!

OBS: Desculpa se o meu código está bagunçado, mas estou realmente tentando fazer esse pequeno programa todos os dias, caso não esteja bom, detalho novamente só que de outra maneira. Abraços! E obrigado por se interessar!

Edited March 19, 2015 at 01:03 AM by Kingflare

[thoga31]

Eu estive a tentar analisar o teu código, assim como a executá-lo, e confesso que não consegui perceber muito bem qual o algoritmo que estás a usar.

Percebi que te estás a basear no meu esquema, mas não entendi por que método o estás a tentar implementar.

Podes comentar o código e, se possível, exemplificar o que estás a tentar fazer?

[Kingflare]

Pronto, está melhor agora?

[thoga31]

Sempre que um anagrama não é repetido, estás a chamar a função principal, "permutarString", e penso que aí esteja parte do problema do ciclo infinito.

Considero o teu código demasiado complexo, e penso que isso é uma fonte de problemas.

Em primeiro lugar, eu separava a questão da repetição para uma função à parte. A prioridade aqui é chegar às permutações, quer tenham repetições ou não.

Quando eu sugeri a chamada recursiva, queria sugerir que as substrings fossem permutadas pela mesma função. Ou seja, se pegarmos em "PERM" e pegar na letra "P", vou aplicar a própria função para permutar "ERM", e assim sucessivamente. Depois de ter usado a letra "P", usava a "E", removia-a de "PERM" e ficava com "PRM", e isto seria também permutado recursivamente.

Explicar o algoritmo das permutações nunca me foi fácil, pelo que, a título excepcional, vou apresentar parte da minha solução ao problema acompanhado de comentários para explicar o algoritmo que antes tentei exemplificar:

type
  TStrArray = array of string;

function Perm(const xs : string) : TStrArray;
(* Returns total permutations. *)
var
  i  : LongInt;
  x  : char;
  y  : string;
  ys : TStrArray;

begin
  if Length(xs) = 0 then begin
     Perm := nil  // Não faz sentido, retorna NIL
  end else begin
     SetLength(Perm, Fact(Length(xs)));  // Fact(n) é a função que devolve n!, factorial de n
                                         // Nº permutações = (nº elementos)!

     if Length(xs) = 1 then
        Perm[0] := xs  // Um único caracter não tem permutações - devolvemo-lo a ele mesmo
     else begin
        i := 0;
        for x in xs do begin       // Para cada caracter:
           ys := Perm(Rm(x, xs));       // Removê-lo da string e permutar a substring, guardando todas as permutações em ys
                                        //    -> Rm: função que remove o caracter x da string xs e devolve a substring resultante
           for y in ys do begin                 // Para cada permutação presente em ys...
              Perm[i] := Concat(String(x), y);  // ...concatenar com o caracter "seleccionado" e adicionar ao array de resultados.
              Inc(i);
           end;
        end;
     end;
  end;
end;

Esta função devolve todas as permutações, inclusive as repetidas. Uma função adicional terá de ser usada para "limpar" os resultados desta função.

Edited March 21, 2015 at 06:35 PM by thoga31

[Kingflare]

Olá, thoga! Tudo bem? Então depois de muito tentar e ter tentativas falhas, consegui uma simples e que tem um custo computacional não tão elevado quanto a da outra maneira que eu estava fazendo, segue:

Program pascal;

uses crt;

var
  size:integer;
  arr:string;

procedure permute(a:string; first,size:integer);
var
  i:integer;

procedure swap(var a :string; i,j:integer);
 var
temp: char;
begin
  temp:=a[j];
  a[j]:=a[i];
  a[i]:=temp;
end;

  begin

if (size=first) then begin
   for i:= 1 to size do
	   write(a[i]);
	   writeln();
	end

 else begin

 for i:= first to size do begin
   swap(a,first,i);
   permute(a, first+1,size);
   swap(a,first,i);
 end;
end;
end;

begin
 size:=3;
 arr:='123';
 permute(arr,1,3);
 readkey;
end.

Esse é um exemplo bem simples que o usuário depois pode fazer uma adaptação e colocá-lo pra permutar quantas vezes quiser e quantos termos quiser. Muito obrigado por sua atenção, suas dicas e paciência. Eu tentei da maneira que você me ensinou, mas eu estava errando em algo que não consegui achar. Muito obrigado!

Edited March 26, 2015 at 09:18 PM by Kingflare

[thoga31]

Uma vez que já tens uma solução a trabalhar, deixo o link para a minha solução do problema. 😉

Nota: o meu código usa algumas capacidades do Pascal que não são comummente ensinadas nas escolas ou nas universidades.