« Função para validar Inscrição Estadual (IE) de todos os estados | Home | Validador TD-REDF “Tipo de registro incorreto - Arquivo não UTF8″ »

Arranjo simples - Código delphi - Parte 1

By Paulo (CincoBytes) | January 12, 2008

Na semana passada no news da trollnet* iniciou-se um post sobre Arranjo Simples (análise combinatória); como sobrou um tempinho resolvi escrever um código para gerar as combinações:

Um pouco de teoria

Arranjo simples:

São agrupamentos formados com p elementos, (p<m) de forma que os elementos sejam distintos entre sí pela ordem ou pela espécie; nesse tipo de arranjo não ocorre a repetição de qualquer elemento em cada grupo.

Fórmula:

As(m,p) = m!/(m-p)!

Exemplos:

As(4,2) = 4!/(4-2)! = 4!/(2)! = 24/2 = 12

As(4,3) = 4!/(4-3)! = 4!/(1)! = 24/1 = 24

As(10,10) = 10!/(10-10)! = 10!/(0)! = 3628800/1 = 3.628.800

Sobre o algoritmo:

No principio analisei o resultado de As(4,4) procurando uma formula que permitisse gerar todo o arranjo de uma só vez (não encontrei essa formula), mas percebi que existe um padrão de repetição dado por:

Nº_repetições = Nº_repetições_anteriores / (Nº_elementos - Coluna);

Assim sendo:

Após determinar qual elemento deve ocupar uma determinada posição basta preencher esta coluna N vezes com o mesmo elemento sem que para isso haja a necessidade de testa-lo novamente**. Com esse método foi possível criar um algoritmo pequeno e com bom desempenho.

** Para se ter um idéia em As(10,10) , na primeira coluna, cada um dos 10 elementos se repete 362.880 sem a necessidade de testa-lo todas as vezes.

procedure CriarArranjos(Elementos: string; Tamanho: integer);
var
  i, j, k, Repeticoes, NumeroElementos, Coluna,
    Posicao, TotalArranjos: integer;
  ListaElementos, Elemento: string;
  Arranjo: array of string;
begin
  NumeroElementos := length(Elementos);
  j := 1;
  for i := 1 to NumeroElementos do
    j := j * i;
  k := 1;
  for i := 1 to (NumeroElementos - Tamanho) do
    k := k * i;
  TotalArranjos := j div k;
  Repeticoes := TotalArranjos;
  SetLength(Arranjo, TotalArranjos);
  for Coluna := 0 to Tamanho - 1 do
  begin
    Posicao := 0;
    ListaElementos := Elementos;
    Repeticoes := Repeticoes div (NumeroElementos - Coluna);
    while Posicao < TotalArranjos do
    begin
      if pos(ListaElementos[1], Arranjo[Posicao]) = 0 then
      begin
        Elemento := ListaElementos[1];
        for i := Posicao to Posicao + Repeticoes - 1 do
          Arranjo[i] := Arranjo[i] + Elemento;
        Posicao := Posicao + Repeticoes;
        ListaElementos := copy(ListaElementos, 2, NumeroElementos);
        if length(ListaElementos) = Coluna then
          ListaElementos := Elementos;
      end
      else
        ListaElementos := copy(ListaElementos, 2, NumeroElementos) +
          ListaElementos[1];
    end;
  end;
  // Usar o array como quiser //
end;

* Utilize o seu newsreader para participar do news da trollnet. (servidor: trollnet.no-ip.org - grupo:vntc.linguagens.delphi)

PS: Vasto material pode ser encontrado internet relacionados a matemática, análise combinatória e loterias.

Ver: Arranjo simple - Código delphi - Parte 2…

Topics: Delphi, Todos |

Comments