Array
(
)

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

Djorius
   - 13 jan 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:

#Código


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?


Michael
   - 13 jan 2006

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


Edilcimar
   - 14 jan 2006

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


Marco Salles
   - 14 jan 2006

#Código

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 Memo1.Lines.Add(s); 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..


Edilcimar
   - 14 jan 2006

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


Marco Salles
   - 14 jan 2006


Citação:
do jeito que vc fez você teria um resultado de 8,8,8


:arrow: Teste ai.... :wink: O Controle do Fluxo do loop é interno ..

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

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

#Código

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 tecnica e a primeira e mais didática..

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

Sem as variaveis a,b ficaria ssim :


Citação:
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;



Edilcimar
   - 14 jan 2006

Ok, tem razão!