dúvida com algoritmo de análise combinatória

13/01/2006

fala galera. não estou conseguindo desenvolver um algoritmo. imaginem o seguinte: eu tenho 8 números (1,2,3,4,5,6,7,8). eu queria listar todas as combinações possíveis entre esses números (em grupos de 3) em um memo. fiz o seguinte:

var i,j,k:integer;
    s:string;
begin
   Memo1.Lines.Clear;
   for i := 1 to 8 do
   begin
      for j := 1 to 8 do
      begin
         for k := 1 to 8 do
         begin
            s := IntToStr(i)+´,´+IntToStr(j)+´,´+IntToStr(k);
            if (Memo1.Lines.IndexOf(s) < 0) then Memo1.Lines.Add(s);
         end;
      end;
   end;
   Label1.Caption := ´Total de combinações: ´+IntToStr(Memo1.Lines.Count);
end;


esse código vai me retornar:
1,1,1
1,1,2
1,1,3
1,1,4
2,4,5
6,4,8
etc.

só que tem um problema. dessa forma está me retornando alguns resultados que eu não quero. por exemplo:

1) está retornando as possibilidades onde os números são iguais (2,2,2)

2) está me retornando as possibilidades que já foram mostradas em outra
ordem. por exemplo: ele já tinha adicionado (1,2,3) logo eu não queria que fosse adicionado (3,2,1) ou então (2,1,3) ou (2,3,1), entendem?

alguém poderia me dar um help?


Djorius

Respostas

13/01/2006

Michael

Olá!

Isso é mais um problema de matemática do que de programação... ;-)

O algoritmo matemático seria esse: [u:850791a06d]8[/u:850791a06d] [u:850791a06d]7[/u:850791a06d] [u:850791a06d]6[/u:850791a06d], onde cada número indica a quantidade de digitos diferentes que cada posição do numeral pode ter. Desta forma casos repetidos como o 222 ou 123 e 321, que vc citou não vão entrar na soma de anagramas.

Acho q isso já te dá uma luz para re-implementar seu algoritmo em Delphi, certo? ;-)

[]´s


Responder Citar

14/01/2006

Edilcimar

para combinar 8 número 3 a 3
for I := 1 to 6
for J := I+1 to 7
for K := J+1 to 8


Responder Citar

14/01/2006

Marco Salles

procedure TForm1.Button2Click(Sender: TObject);
var
s:string;
 i,j,k:integer;
 a,b:integer;
 TS: TStrings;
begin
   Memo1.Lines.Clear;
    TS := TStringList.Create;
   for i := 1 to 8 do
   begin
       a:=i+1;
       b:=i+2;
      for j := a to 8 do
      begin
         for k := b to 8 do
         begin
            s := IntToStr(i)+´,´+IntToStr(j)+´,´+IntToStr(k);
            TS.Add(s);
         end;
          b:=b+1;
      end;
      a:=a+1;
   end;
   Memo1.Lines.Assign(TS);
   TS.Free;
   Label1.Caption := ´Total de combinações: ´+IntToStr(Memo1.Lines.Count);
end;


Não use o [b:bc163072e2] Memo1.Lines.Add(s); [/b:bc163072e2] a cada iteração , isto causa uam interface ruim , alem de aumentar consideravelmente o tempo de resposta... No seu caso , com são poucas combinações , isto pode ser um pouco impreceptivel , mas para quantidades maiores o tempo gasto no processamento aumenta consideravelmente... Use uma TString , assim voce so atualiza a interface uma unica vez No final..


Responder Citar

14/01/2006

Edilcimar

Marcos, em combinação vc não pode ter números repetidos, por isto coloquei aquelas limitações que você desconsiderou, do jeito que vc fez você teria um resultado de 8,8,8


Responder Citar

14/01/2006

Marco Salles

do jeito que vc fez você teria um resultado de 8,8,8


:arrow: [b:baa41687f0]Teste ai[/b:baa41687f0].... :wink: O Controle do Fluxo do loop é interno ..

tem o controle interno , devido as variáveis [b:baa41687f0]a,b[/b:baa41687f0] qu impede números como [b:baa41687f0]8,8,8 [/b:baa41687f0]... [b:baa41687f0]1,23 e 3,2,1[/b:baa41687f0] etc...

:idea: :idea:
que dá o mesmo efeito de fazer assim

for I := 1 to 8 
for J := I+1 to 8 
for K := J+1 to 8


que também é um controle interno do fluxo.. A unica diferença que a segunda implementação é mais[b:baa41687f0] tecnica [/b:baa41687f0]e a primeira e mais [b:baa41687f0]didática..[/b:baa41687f0]

Foi isto que eu quis passar , alem de concordar inteiramente com a sua postagem

Sem as variaveis [b:baa41687f0]a,b[/b:baa41687f0] ficaria ssim :

procedure TForm1.Button1Click(Sender: TObject); var s:string; i,j,k:integer; TS: TStrings; begin Memo1.Lines.Clear; TS := TStringList.Create; for i := 1 to 6 do begin for j := i+1 to 7 do begin for k:=j+1 to 8 do begin s := IntToStr(i)+´,´+IntToStr(j)+´,´+IntToStr(k); TS.Add(s); end; end; end; Memo1.Lines.Assign(TS); TS.Free; Label1.Caption := ´Total de combinações: ´+IntToStr(Memo1.Lines.Count); end;



Responder Citar

14/01/2006

Edilcimar

Ok, tem razão!


Responder Citar