DevMedia
Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Para efetuar o download você precisa estar logado. Clique aqui para efetuar o login
post favorito     comentários

Análise Combinatória - Como listar as combinações de uma binomial simples

Neste artigo veremos como trabalhar com análise combinatória, listando combinações de uma binomial simples usando o Delphi.

[fechar]

Você não gostou da qualidade deste conteúdo?

(opcional) Você poderia comentar o que não lhe agradou?

Confirmo meu voto negativo

Uma Binomial Simples pode ser usada para muitas coisas. Um exemplo bem simples e muito próximo de todos é a combinação de números da Mega Sena. Se uma pessoa desejar fazer uma aposta em 12 dezenas (sabemos que o máximo são 6 dezenas em cada cartão) vai ter de marcar 924 cartões diferentes e ter muito trabalho para não repetir nenhum cartão. Eu já havia feito um programa para a Mega Sena, mas fiz esse outro porque precisei gerar uma série de combinações binomiais com tamanhos de conjuntos diferentes e achei interessante compartilhar, pois várias pessoas já devem ter passado por esse problema.

A Binomial

Para quem não se lembra bem como é uma Binomial Simples, segue uma breve explicação. Uma Binomial Simples permite calcular quantas combinações de sub-conjuntos de tamanho K sem repetição existem para um conjunto de tamanho N. Por exemplo: se desejamos combinar o conjunto N=4 {a,b,c,d} em conjuntos K=2, teremos os seguintes pares:

{(a,b), (a,c), (a,d), (b,c), (b,d) e (c,d)}.

 

A fórmula da Binomial é a seguinte:

 

Figura 1.

O Algoritmo

De longe, a parte mais complexa deste programa é o sequenciador, que permite gerar as combinações sem repetições e, para essa função, usei um processo recursivo que se mostrou bastante eficiente. A lógica é a seguinte: a função recebe um parâmetro que é a posição do ítem K que deve ser incrementado. Por exemplo: para a sequência acima temos 2 ítens. Você pode notar que o primeiro ítem ‘a’ se repete até que o segundo ítem alcance o elemento ‘d’. Então ‘a’ deve passar a ‘b’. Esse processo torna-se tão complexo quanto maior o número de elementos de K. A variável max_values guarda os limites superiores dos elementos de K. No caso acima max_values = [3,4] e a variável combination guarda o índice da combinação atual.

 

Gerador de Sequencias:

 

procedure next_combination (pos: integer);

begin

  if (pos = 0) then Exit;

  inc (combination[pos]);

  if (combination[pos] > max_values[pos]) then begin

     next_combination (pos - 1);

     combination[pos] := combination[pos - 1] + 1;

  end;

end;

Interface com o usuário

A interface do programa é bem simples e pede três parâmetros: os valores de N e K e os valores que queremos fazer as combinações. Por exemplo, podemos usar nomes de times de futebol para preparar uma tabela de jogos ou números da Mega Sena. Enfim, qualquer tipo de informação numérica ou textual. Veja Figura 2.

 

Figura 2. Interface com o usuário

Abaixo segue a listagem completa do programa, veja Listagem 1.

 

Listagem 1. Descrição da listagem

unit binomial_generator;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, ExtCtrls;

 

type

  TfrmGenerator = class(TForm)

...

    procedure Button1Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

 

var

  frmGenerator: TfrmGenerator;

  N, K: Integer;

  values: Array [1..100] of string;

  max_values: array[1..100] of Integer;

  combination: array[1..100] of Integer;

 

procedure generate (N, K: Integer);

 

implementation

{$R *.dfm}

//------------------------------------------------------------------------------

procedure TfrmGenerator.Button1Click(Sender: TObject);

var s: String;

    i: Integer;

begin

  N := StrToInt (Edit1.Text);

  K := StrToInt (Edit3.Text);

  s := Edit2.Text;

  s := s + ',';

  for i := 1 to N do begin

      values[i] := Copy (s, 1, Pos(',', s)-1);

      delete (s, 1, Pos(',', s));

  end;

  for i := 1 to K do begin

      max_values[K-i+1] := N-i+1;

      combination[i] := i;

  end;

  generate (N, K);

end;

//------------------------------------------------------------------------------

procedure next_combination (pos: integer);

begin

  if (pos = 0) then Exit;

  inc (combination[pos]);

  if (combination[pos] > max_values[pos]) then begin

     next_combination (pos - 1);

     combination[pos] := combination[pos - 1] + 1;

  end;

end;

//------------------------------------------------------------------------------

function fat (n: Integer):Integer;

var i: Integer;

begin

  Result := 1;

  for i := 2 to n do

      Result := Result * i;

end;

//------------------------------------------------------------------------------

procedure generate (N, K: Integer);

var n_comb, i, j: Integer;

    f: TextFile;

    s: String;

begin

  n_comb := fat (N) div (fat(K) * fat(N-K));

  ShowMessage ('Number of Combinations: ' + IntToStr (n_comb));

  Screen.Cursor := crHourGlass;

  AssignFile (f, ExtractFilePath (ParamStr (0)) + 'out.csv');

  ReWrite (f);

  for i := 1 to n_comb do begin

      s := '';

      for j := 1 to K do

          s := s + values[combination[j]] + ';';

      WriteLn (f, s);

      next_combination (K);

  end;

  CloseFile (f);

  Screen.Cursor := crDefault;

end;

end.

Conclusões

Depois de algumas vezes em que me vi diante desse problema, decidi procurar algumas coisas na Web, mas não encontrei. Então, optei por gastar algumas horas para desenvolver o programa. Aparentemente simples, pode ser muito complexo se a rotina do sequenciador não utilizar o modelo de recursividade. Acho interessante também como um exercício teórico de algorítmo.

 

Alexandre Crivellaro (acrivellaro@gmail.com) é diretor de tecnologia do grupo IBOPE, formado em matemática e computação com especialização em visão computacional e desenvolve software nas horas vagas.

O que você achou deste post?
Conhece a assinatura MVP?
Publicidade
Serviços

Mais posts