[Resolvido] Combinação

[trebew 0]

Boa tarde... se alguem puder ajudar...

 

 

Dado um conjunto S = {01, 03, 04, 08, 13, 17}, o que desejo é fazer a combinação (no sentido matemático da coisa, não no sentido vulgar) destes elementos. Por exemplo a combinação C(6,3). Temos que C(n,p) = n!/((n-p)!*p!), logo C(6,3) = 6!/((6-3)!*3!) = 20. Temos então possibilidades diferentes, quais sejam:

 

{01, 03, 04}, {01, 03, 08}, {01, 03, 13}, {01, 03, 17}, {01, 04, 08}, {01, 04, 13},

{01, 04, 17}, {01, 08, 13}, {01, 08, 17}, {01, 13, 17}, {03, 04, 08}, {03, 04, 13},

{03, 04, 17}, {03, 08, 13}, {03, 08, 17}, {03, 13, 17}, {04, 08, 13}, {04, 08, 17},

{04, 13, 17}, {08, 13, 17}

 

Note que {01, 04, 03} não é um resultado desejado visto que é uma repetição de {01, 03, 04} conforme a definição de combinação.

Alguém sabe alguma técnica em algoritmos para este tipo de problema? Gerar todas as possíveis combinações?

 

Eu construi a solução utilizando uma árvore, apenas ainda não consegui fazer isso em um algoritmo...

 

 

Obrigado!

[quitZAUMMM 18]

Tente algo q te ajudamos..

vai postando.

 

[]s

[trebew 0]

Bom... depois de pensar um pouco a respeito do assunto cheguei a conclusão de que o melhor é utilizar uma estrutura de árvore mesmo, como fiz manualmente no desenho do post anterior. Me deparei com outro problema, não encontrei uma classe em delphi que implemente uma árvore. Tem o TreeView, mas é um componente visual e creio que não se encaixa muito bem. Então o que estou fazendo é escrevendo uma classe para descrever a estrutura.

Implementei duas classes: TArvore e TNode. TNode guarda as informações de cada nó, sendo 4 informações: o próprio nó, o pai do nó, o filho mais velho (o mais da direita no desenho), e o próximo filho (o ultimo recebe nil para indicar que não há mais filhos naquele nível). TArvore possui um vetor que guarda todos os nós, um valor que guarda a quantidade de níveis da árvore (os níveis são cada linha da árvore, na figura).

Meu atual problema está sendo com um método que percorra toda árvore e imprima, guarde cada ramo separadamente.

 

Vamos analisar somente a árvore número três da figura acima:

Achei em livros métodos que percorrem a árvore e imprimem da seguinte maneira: 04 08 13 17 13 17

Porém eu quero percorre-la e imprimir/guardar assim: {04, 08, 13}, {04, 08, 17}, {04, 13, 17}

Para isso criei o método getRamos(), que ainda não tem nada escrito!

 

Ai depois ainda vem o problema de como gerar as árvores de modo a cumprir a tarefa em questão, a combinação C(n,p)

 

Mas já consegui elaborar um idéia, então está tranquilo. O que queria mesmo era ver se alguem teria uma idéia pra sugerir...

 

{ Classe que implementa um nó de uma árvore }
{ Escrito por: Webert Brito dos Passos, Eng. Eletricista }
{ Última atualização: 30/04/11 17:17 }

unit Node;

interface

type
 TNode = Class(TObject)
 private
   info: ^Integer;   { ponteiro para o nó }
   pai: ^Ingeter;    { ponteiro para o pai }
   filho: ^Integer;  { ponteiro para o filho mais velho }
   prox: ^Integer;   { ponteiro para o próximo filho mais velho }
 public
   constructor Create(var inf, p, f, pr: Integer);
   function getInfo() : Integer;
   function getPai() : Integer;
   function getFilho() : Integer;
   function getProx() : Integer;
   procedure setInfo(i: Integer);   { i é o endereço de info }
   procedure setPai(p: Integer);    { p é o endereço de pai }
   procedure setFilho(f: Integer);  { f é o endereço de filho }
   procedure setProx(pr: Integer);   { pr é o endereço de prox }
 end;

implementation

{ Os parametros são os endereços, e não os valores }
constructor TNode.Create(var inf, p, f, pr: Integer);
begin
 inherited;
 info := inf;
 pai := p;
 filho := f;
 prox := pr;
end;

function TNode.getInfo() : Integer;
begin
 Result := info^;
end;

function TNode.getPai() : Integer;
begin
 Result := pai^;
end;

function TNode.getFilho() : Integer;
begin
 Result := filho^;
end;

function TNode.getProx() : Integer;
begin
 Result := prox^;
end;

procedure TNode.setInfo(i: Integer);   { i é o endereço de info }
begin
 info := i;
end;

procedure TNode.setPai(p: Integer);    { p é o endereço de pai }
begin
 pai := p;
end;

procedure TNode.setFilho(f: Integer);  { f é o endereço de filho }
begin
 filho := f;
end;

procedure TNode.setProx(pr: Integer);   { pr é o endereço de prox }
begin
 prox := pr;
end;

end.

 

{ Classe que implementa uma árvore }
{ Escrito por: Webert Brito dos Passos, Eng. Eletricista }
{ Última atualização: 30/04/11 17:17 }

Unit Arvore;

interface

uses Node;

type
 TArvore = Class(TObject)
 private
   //conjN: array of Integer; { Conjunto com os elementos que compõem a árvore }
   nos: array of TNode;     { A árvore em si, seus nós }
   p: Integer;  { Quantidade de níveis da árvore }
 public
   constructor Init(niveis: Integer{conjN: array of Integer});
   procedure addNode(nextNode: TNode);
   { Cada ramo será armazenda em uma linha, logo uma linha terá p colunas }
   function getRamos() : array of array of Integer;

   { Quantidade de nos que a árvore contém }
   function getQdeRamos() : Integer;
end;

implementation

constructor TArvore.Init(niveis: Integer{conj: array of Integer});
begin
 inherited;
 p := niveis;
 //conjN := conj;
 {nos := ; }
end;

{ Os valores nas variaveis de nó guardam apenas o endereço para o valor real }
procedure TArvore.addNode(nextNode: TNode);
begin
 SetLength(nos,Length(nos)+1);
 nos[Length(nos)-1] := nextNode;
end;

function TArvore.getRamos(): array of array of Integer;
var
 i: Integer;
 ramos: array of array of Integer;
begin
 { Inicializando a Matriz que conterá os ramos }
 { Cada linha da matriz representa um ramo completo da árvore, desde a raiz até a folha. Ex: {04, 08,13} da árvore acima no post }
 { A quantidade de colunas é a quantidade de níveis da árvore }
 { Se se trata uma combinação C(6,3) temos uma matriz com C(6,3) = 20 linhas e 3 colunas 20x3 }
 SetLength(ramos, getQdeRamos());
 for i := 0 to Length(nos) - 1 do begin
   SetLength(ramos[i], p);
 end;


end;

function TArvore.getQdeRamos();
begin
 Result := Length(nos);
end;

end.