VB .NET - Calculando Permutações


Hoje vamos falar sobre Permutações.

Se você não fugiu da escola, deve lembrar das aulas de matemática quando algum dia alguém tentou lhe ensinar a calcular permutações.

Vamos então começar lembrando a teoria iniciando com o conceito sobre arranjos...

Arranjos

Arranjos são agrupamentos nos quais a ordem dos elementos faz diferença.

Por exemplo, os números de três algarismos formados pelos elementos {1,2 e 3} são:

312, 321, 132, 123, 213, 231

Esse agrupamento é um arranjo, pois a ordem dos elementos 1, 2 e 3 é diferente; È considerado arranjo simples, pois os elementos não se repetem.

Para que tenhamos arranjos simples é preciso ter um conjunto de elementos distintos com uma quantidade qualquer de elementos, sendo que os arranjos simples formados irão possuir n elementos, e essa quantidade será igual ou menor que a quantidade de elementos do conjunto.

Permutação

O conceito de permutação expressa a idéia de que objetos distintos podem ser arranjados em inúmeras ordens distintas.

Assim, seja um conjunto A com n elementos; chamamos de permutação a todo arranjo com n elementos retirados de A.

A cada um dos agrupamentos que podemos formar com certo número de elementos distintos, tal que a diferença entre um agrupamento e outro se dê apenas pela mudança de posição entre seus elementos, damos o nome de permutação simples.

Exemplos:

1) Seja A um conjunto com os elementos {a, b, c}.

As permutações possíveis de A são: {(a,b,c);(a,c,b);(b,a,c);(b,c,a);(c,a,b);(c,b,a)}. Total de 6 permutações.

2) Quantos anagramas possui a palavra OBA ?

As permutações da palavra são: {(OBA;(OAB);(BAO);(BOA);(ABO);(AOB)}. Total de 6 permutações.

Assim para obter o número de permutações com m elementos distintos de um conjunto, basta escolher os m elementos em uma determinada ordem.

O número de permutações de m elementos será expresso por : P(m)

A expressão para seu cálculo será dada por:   P(m) = m(m-1)(m-2)...(m-p+1)...3.2.1

Podemos também escrever :    A(m,m) = P(m)

O Arranjo de m elementos dos quais m elementos participam é igual a Permutação destes elementos.

Uma forma simplificada de expressar a permutação de m elementos é através do fatorial: P(m) = m!

Este símbolo de exclamação posto junto ao número m é lido como o fatorial de m, onde m é um número natural.

O fatorial de um número inteiro não negativo pode ser definido de uma forma recursiva através da função P=P(m) ou com o uso do sinal de exclamação:

(m+1)! = (m+1).m!     Ex: 3! = 3.2.1!   =>  que é a mesma coisa que : 3.2.1 = 6

Nota : Lembrando que : 0! = 1   (o fatorial de zero é igual a 1)   e que 1! = 1 ( o fatorial de 1 é igual a 1)

Com isso creio que já deu para recordar o básico sobre arranjo e permutação simples.

Vamos então ao que realmente interessa...

Como podemos fazer para implementar o cálculo de permutações simples no Visual Basic ?

Calculando permutações com o Visual Basic

Vou mostrar duas possibilidades de calcular permutações usando a linguagem Visual Basic através do Visual Basic 2010 Express Edition.

1- Calculando as permutações de um valor numérico

Na primeira eu vou mostrar como podemos calcular quantas permutações podemos realizar com um determinado valor numérico.

Neste caso irei informar um valor numérico e irei obter a quantidade de permutações possíveis sendo que as possíveis permutações serão exibidas em um controle ListBox.

A interface do programa é bem simples e possui apenas uma caixa duas caixas de texto, um Button e um ListBox.

Abaixo vemos o programa em execução exibindo o resultado para a permutação de 4 elementos:

fig 1.0

Abra o VB 2010 Express Edition e crie um novo projeto do tipo Windows Forms Application com o nome Permutacoes;

A seguir no formulário padrão inclua os seguintes controles: 2 Labels, 2 TextBox, 1 Button e 1 ListBox conforme o leiaute acima (fig 1.0):

A seguir inclua o código abaixo no formulário form1.vb:

Public Class Form1
    Private NumeroValores As Integer
    Private m_Usado() As Integer
    Private m_SolucaoAtual() As Integer

    Private Sub btnCalcular_Click(ByVal sender As System.Object, ByVal e 
As System.EventArgs) Handles btnCalcular.Click
        lstResultados.Items.Clear()
        Application.DoEvents()

        'define quantos valores serão permutados
        NumeroValores = Val(txtNumeroItens.Text)
        ReDim m_Usado(NumeroValores)
        ReDim m_SolucaoAtual(NumeroValores)
        EnumeraValores(1)
        txtCombinations.Text = Format$(Factorial(NumeroValores))
    End Sub

    Private Sub EnumeraValores(ByVal index As Integer)
        ' Verifica se existe qualquer valores 
        If index > NumeroValores Then
            ' Todos os valores são usados
            ' Obtem uma string para a solução
            Dim resultado As String = ""
            For i As Integer = 1 To NumeroValores
                resultado &= Format$(m_SolucaoAtual(i))  & " "
            Next i
            ' Inclui a solução a lista
            lstResultados.Items.Add(resultado)
            Exit Sub
        End If
        ' Examina cada valor
        For i As Integer = 1 To NumeroValores
            ' Verifica se o valor ja foi usado
            If Not m_Usado(i) Then
                ' Se nao foi usado tente usá-lo
                m_Usado(i) = True
                m_SolucaoAtual(index) = i
                EnumeraValores(index + 1)
                m_Usado(i) = False
            End If
        Next i
    End Sub

    Private Function Factorial(ByVal num As Long) As Long
        Dim resultado As Long = 1
        For i As Integer = 2 To num
            resultado *= i
        Next i
        Return resultado
    End Function
End Class

Neste código temos duas funções que são chamadas a partir do evento Click do botão Calcular :

2- Calculando as permutações

Nesta solução vamos calcular a permutação simples possíveis para os itens informados.

O usuário deverá informar os itens separados por vírgulas em uma caixa de texto no formulário da aplicação e as permutações serão calculadas e exibidas.

A interface do programa é similar a usada no programa anterior e nas figuras abaixo vemos o programa em execução mostrando o resultado as permutações para a palavra CASA (anagrama) e para os números 20,11,15,13,80:

Abra o VB 2010 Express Edition e crie um novo projeto do tipo Windows Forms Application com o nome Permutacoes2;

A seguir no formulário padrão inclua os seguintes controles: 2 Labels, 2 TextBox, 1 Button e 1 ListBox conforme o leiaute acima:

A seguir inclua o código abaixo no formulário form1.vb:

Public Class Form1
    'Gera e exibe permutações
    Private Sub btnCalcular_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) 
Handles btnCalcular.Click

        lstResultados.Items.Clear()
        txtPermutacoes.Text = ""
        Application.DoEvents()

        Dim matriz() As String
        matriz = txtValores.Text.Split(",")

        'Genera uma coleção para permutar
        'define o total de elementos a permutar
        Dim num_valores As Integer = Val(matriz.Length)
        Dim valores As New Collection

        'Atribui os valores informados aos valores
        For i As Integer = 0 To num_valores - 1
            valores.Add(matriz(i))
        Next i

        ' Gera as permutações para o no de elementos informados
        Dim permutacoes As Collection = GeraPermutacoes(valores)

        ' Exibe o resultado 
        For Each p As Collection In permutacoes
            Dim texto As String = ""
            For Each item As Object In p
                texto &= item.ToString()
            Next item
            lstResultados.Items.Add(texto)
        Next p

        txtPermutacoes.Text = Format$(Factorial(num_valores))
    End Sub

    ' Retorna o fatorial do número
    Private Function Factorial(ByVal num As Long) As Long
        Dim resultado As Long = 1
        For i As Integer = 2 To num
            resultado *= i
        Next i
        Return resultado
    End Function

    ' Gera as permutacoes de valores na coleção valores
    ' Retorna o resultado através da coleção 
    Private Function GeraPermutacoes(ByVal valores As Collection) As Collection
        Dim resultados As New Collection
        ' Verifica se existe um único valor
        If valores.Count = 1 Then
            ' Retorna uma coleção contendo 
            ' a permutação igual a valor único
            resultados.Add(New Collection)
            resultados.Item(1).Add(valores.Item(1))
            Return resultados
        End If

        ' Cria as permutações iniciando com cada primeiro item
        resultados = New Collection
        Dim num_valores As Integer = valores.Count
        For i As Integer = 1 To num_valores
            ' Salva o valor
            Dim primeiro_valor As Object = valores.Item(i)

            ' Remove o item.
            valores.Remove(i)

            ' Gera as permuatações dos valores restantes
            Dim nova_permutacoes As Collection = GeraPermutacoes(valores)

            ' Faz a permutação incluino o primeiro_valor
            ' no inicio de cada nova permutação
            For j As Integer = 1 To nova_permutacoes.Count
                ' Inclui o primeiro item
                Dim novo_resultado As New Collection
                novo_resultado.Add(primeiro_valor)
                ' Inclui o resto dos itens na nova permutação
                For k As Integer = 1 To nova_permutacoes(j).Count
                    novo_resultado.Add(nova_permutacoes(j).Item(k))
                Next k

                ' Inclui esta nova permutação aos resultados
                resultados.Add(novo_resultado)
            Next j

            ' Restaura o valor removido
            If i > valores.Count Then
                valores.Add(primeiro_valor)
            Else
                valores.Add(primeiro_valor, , i)
            End If
        Next i

        ' Retorna o resultado
        Return resultados
    End Function
End Class

O código acima possui duas funções que são chamadas a partir do evento Click do botão Calcular Permutações :

Código é trivial e esta comentado mas alerto para fato de que ele não esta otimizado, e para um número maior de itens (maior que 9) o sistema poderá ficar lento e até travar.

Fica como exercício a otimização dos código se realmente isso for de seu interesse.

Pegue os projetos completos aqui : Permutacaoes.zip e Permutacoes2.zip

Eu sei é apenas VB .NET mas eu gosto...

"Graças e Paz da parte de Deus Pai e da de nosso Senhor Jesus Cristo. O qual se deu a si mesmo por nossos pecados para nos livrar do presente século mau, segundo a vontade de Deus nosso Pai, ao qual glória para todo o sempre, Amém."  Gálatas 3-5

Referências:


José Carlos Macoratti