Algoritmos – Parte 02 – Permutações

Introdução

No post anterior (Algoritmos – Parte 01 – Loterias), vimos a criação de um algoritmo para realizar combinações simples, que pode ser usado na maioria das loterias numéricas. Agora, vamos ver um algoritmo de permutação — Algoritmo de Heap — e ver como fazer a portabilidade de um pseudo-código para AdvPL.

Algoritmo de Heap

O Algoritmo de Heap é até hoje a forma mais optimizada de gerar todas as possibilidades de permutações em um conjunto de elementos. A permutação é um processo pelo qual podemos criar sequências não repedidas dos elementos de um conjunto, alterando a sua ordem. Por exemplo, partindo de um conjunto de três números (1, 2 e 3), podemos criar as seguintes permutações:

1 2 3 
1 3 2 
2 1 3
2 3 1 
3 1 2
3 2 1

Calcula-se o número total de possibilidades de permutação de um conjunto com a fórmula P(m) = m! –> Onde P é o número de possibilidades de permutação e m é o número de elementos do conjunto, e  “!” é o símbolo da operação fatorial. Por exemplo, em um conjunto de 3 elementos, temos 3! ( 3! = 3*2 = 6) conjuntos ordenados resultantes.

Pseudocódigo

A partir da Wikipedia, por exemplo, podemos obter o pseudocódigo do algoritmo — uma representação em linguagem quase natural da sequência de operações nos conjuntos de dados para se chegar ao resultado. Esta versão do pseudo-código é a não-recursiva.

procedure generate(n : integer, A : array of any):
    c : array of int

    for i := 0; i < n; i += 1 do
        c[i] := 0
    end for

    output(A)

    i := 0;
    while i < n do
        if  c[i] < i then
            if i is even then
                swap(A[0], A[i])
            else
                swap(A[c[i]], A[i])
            end if
            output(A)
            c[i] += 1
            i := 0
        else
            c[i] := 0
            i += 1
        end if
    end while

Agora, vamos converter isso para AdvPL, primeiro de uma forma bem simples, depois de uma forma mais elaborada. Inicialmente, vamos fazer uma tradução “crua” para o AdvPL, porém funcional.

STATIC Function Generate( n , A )
Local c := {} , i
For i := 1 to n
  aadd(c,0)
Next
output(A)
i := 0 
While i < n
  If  c[i+1] < i
    if ( i % 2 ) == 0 
      swap(A, 1 , i+1)
    else
      swap(A, c[i+1]+1, i+1)
    end if
    output(A)
    c[i+1]++
    i := 0
  Else
    c[i+1] := 0
    i++
  EndIf
Enddo


STATIC Function swap(aData,nPos1,nPos2)
Local nTemp := aData[nPos1]
aData[nPos1] := aData[nPos2] 
aData[nPos2] := nTemp
Return

STATIC Function output(A)
Local i, R := ''
For i := 1 to len(A)
  If !empty(R)
    R += ', '
  Endif
  R += cValToChaR(A[i])
Next
conout(R)
Return

Diferenças na Implementação

A primeira diferença nós vemos logo de início ao usar os Arrays em AdvPL. O pseudo-código parte da premissa que um Array de N posições é endereçado de 0 a N-1 — Isto é, o primeiro elemento do Array é o elemento 0 (zero.) Já em AdvPL, o primeiro elemento do array é 1 (um). Logo, nós mantemos toda a lógica do programa inicial, inclusive as variáveis como se o array fosse base 0 (zero), porém na hora de endereçar os elementos do array, somamos uma unidade. Logo:

if c[i] < i

foi transformado para

if c[i+1] < i

A função swap() tem como objetivo trocar os elementos do array, um pelo outro. Como em AdvPL os arrays são passados por referência, podemos implementar a função de troca guardando o valor do elemento informado em uma variável local, depois atribuímos o conteúdo do segundo elemento informado sobre o primeiro, e então atribuímos o conteúdo salvo do primeiro elemento no segundo — vide função swap(). O diferencial dela em relação ao pseudocódigo é que eu passo para ela em AdvPL três parâmetros: O Array, e as duas posições a serem trocadas.

No pseudo-código, para verificar se um determinado numero é par (even em inglês), pode ser em AdvPL verificando  se o resto da divisão por dois é zero. Para isso, poderíamos usar a função mod(), ou de forma mais prática, o operador “%”.

if ( i % 2 ) == 0

Outro ponto de atenção é justamente a chamada da função swap() quando o número não for par. Veja no pseudocódigo:

swap(A[c[i]], A[i])

Agora, em AdvPL, a implementação ficou assim:

swap(A, c[i+1]+1, i+1)

Reparem que o array c[] guarda uma posição de um array. Como estamos trabalhando com array em base 1, eu devo somar 1 para recuperar o elemento do array c, e como o seu resultado será usado para indicar uma posição do array A[], eu também preciso somar 1.

Já a função output(), cujo entendimento óbvio é mostrar um dos conjuntos obtidos na permutação, implementamos simplesmente recebendo o Array , e criando uma string com o conteúdo de seus elementos separados por vírgula. Para testar o fonte acima, vamos usar a seguinte função:

User Function Permuta()
Generate( 4 , {'A' ,'B' ,'C' ,'D' } )
Return

Após salvarem, compilarem e executarem o programa acima, o resultado no log de console do Protheus Server deve ser:

A, B, C, D
B, A, C, D
C, A, B, D
A, C, B, D
B, C, A, D
C, B, A, D
D, B, A, C
B, D, A, C
A, D, B, C
D, A, B, C
B, A, D, C
A, B, D, C
A, C, D, B
C, A, D, B
D, A, C, B
A, D, C, B
C, D, A, B
D, C, A, B
D, C, B, A
C, D, B, A
B, D, C, A
D, B, C, A
C, B, D, A
B, C, D, A

Conclusão

Vendo o fonte assim, prontinho, parece fácil. Porém, eu comecei resolvendo trocar o nome das variáveis da implementação em AdvPL ao transcrever o pseudocódigo, e o programa não gerava os números corretamente. Joguei fora a primeira versão e parti do código original, mantendo o nome das variáveis, então funcionou.

Novamente agradeço a todos pela audiência e desejo a todos TERABYTES DE SUCESSO !!! 

Referências

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google

Você está comentando utilizando sua conta Google. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s