« Validador TD-REDF “Tipo de registro incorreto - Arquivo não UTF8″ | Home | Como utilizar o LockBox para gerar EAD / CAT-52 / Delphi »

Arranjo simples - Código delphi - Parte 2

By Paulo (CincoBytes) | January 26, 2008

Este artigo é a seqüência do publicado no dia 12 de Janeiro… de lá para cá consegui algum tempo livre e melhorei o algoritmo obtendo um redução de 55% no tempo de processamento conforme descrito abaixo:

As(10,7) = 604.800 combinações (em um P4 1.8Ghz 512MB + Turbo Delphi)

Algoritmo anterior: ~ 1850ms (327.000 combinações/seg)

Algoritmo atual: ~ 833ms (730.000 combinações/seg)

Sobre o algoritmo

Após observar o resultado de um As(5,5) percebi que cada bloco de arranjos (determinados por seu primeiro elemento) se repetia nos próximos blocos apenas com deslocamento do elemento eleito para a esquerda. Assim sendo, notei que não há a necessidade de calcular todas a combinações, mas apenas as combinações do primeiro bloco; depois é só repetir e substituir!

ABCDE
ABCED
ABDCE
…
BACDE
BACED
BADCE
…
CABDE
CABED
CADBE
…

Segue o código…

procedure Arranjo(Elementos: string; Tamanho: integer);
var
  i, j, k, nElementos, posicao, tArranjos, maximo: integer;
  coluna, repeticoes, pElemento: integer;
  cElementos: string;
  arranjo: array of string;
  bloco: array of array of string;
begin
  nElementos := length(elementos);
  j := 1;
  for i := 1 to nElementos do
    j := j * i;
  k := 1;
  for i := 1 to (nElementos - tamanho) do
    k := k * i;
  tArranjos := j div k;
  SetLength(arranjo, tArranjos);
  SetLength(bloco, nElementos, nElementos);
  for i := 0 to nElementos - 1 do
  begin
    cElementos := Elementos[i + 1] +
      StringReplace(Elementos, Elementos[i + 1], '', [rfReplaceAll]);
    for j := 0 to nElementos - 1 do
      bloco[i, j] := cElementos[j + 1];
  end;
  repeticoes := tArranjos;
  maximo := tArranjos div nElementos;
  for coluna := 0 to tamanho - 1 do
  begin
    posicao := 0;
    cElementos := elementos;
    repeticoes := repeticoes div (nElementos - coluna);
    while posicao < maximo do
    begin
      if pos(cElementos[1], arranjo[posicao]) = 0 then
      begin
        pElemento := pos(cElementos[1], elementos) - 1;
        for j := 0 to nElementos - 1 do
          for i := posicao to posicao + repeticoes - 1 do
          begin
            k := i + j * maximo;
            arranjo[k] := arranjo[k] + bloco[j, pElemento];
          end;
        posicao := posicao + repeticoes;
        cElementos := copy(cElementos, 2, nElementos);
        if length(cElementos) = coluna then
          cElementos := elementos;
      end
      else
        cElementos := copy(cElementos, 2, nElementos) +
         cElementos[1];
    end;
  end;
  // Usar o array como quiser //
end;

Ver: Arranjo simples - Código delphi - Parte 1…

Um abraço a todos…

Topics: Delphi, Todos |

6 Responses to “Arranjo simples - Código delphi - Parte 2”

  1. jotalinux2 Says:
    May 3rd, 2008 at 9:52 pm

    Em sua função falta acumular os valores nos primeiros loops [ex: j := j * i; = j:= j + (j*1)]
    senão os valores retornados serão sempre nulos na hora de dividir.

  2. Paulo Says:
    May 4th, 2008 at 8:59 pm

    Os loops a que você se refere estão codificados da maneira *correta* e são utilizados determinar o numero total de arrajos; obtido através do calculo
    do fatorial pela formula: n!/(n-k)! (da linha 9 a 16). Obrigado enviar um comentário.

  3. Murilo Says:
    June 9th, 2008 at 12:10 am

    Valewwwwwwwwwwwwwwwwwwwww!
    Esse algoritmo ai salvou minha vida UAHuahuAHUA
    Estou implementando o problema do caixeiro viajante pelo método da força bruta para um trabalho da faculdade e no caso dele precisaria fazer todas as possibilidades possíveis, e como estou meio sem tempo, esse código veio na hora certa.
    Só queria deixar meus agradecimentos, brigadão.
    \o/

  4. Paulo Says:
    November 1st, 2008 at 6:24 pm

    Boas Paulo, geralmente codifico em C. De uma forma geral percebi o teu código, mas não conheço estas funções nas linhas do código. Agradecia que me digas o que fazem.

    SetLength(Arranjo, TotalArranjos);
    pos(ListaElementos[1], Arranjo[Posicao]) = 0
    copy(ListaElementos, 2, NumeroElementos);

    ou o que seria o código em C.

    Obrigado,
    Abraço

  5. Paulo (CincoBytes) Says:
    November 4th, 2008 at 7:14 am

    Boas,

    O código esta em pascal/delphi.

    - SetLength, redimensiona o tamanho do array Arranjo.

    - pos(ListaElementos[1], Arranjo[Posicao]) = 0
    Pos informa se ListaElementos[1] existe em Arranjo[Posicao], se = 0 é porque não existe.

    - copy(ListaElementos, 2, NumeroElementos)
    copia o NumeroElementos da ListaElementos
    a partir da posição 2.

    Quanto a converter para “C” infelizmente eu não sei fazer pois não domino esta linguagem.

    []’s

  6. Paulo Says:
    November 7th, 2008 at 5:04 pm

    Paulo Obgrigado pelo escalrecimento. O teu raciocínio para o cáculo dos arranjos e a tua obs da repetição dos blocos é revela inteligência. TKS

Comments