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.
