VBA - Dúvida dos leitores 001 - Gerando combinações de números

Gerando combinações de números

A leitora Eliana Miranda nos mandou a seguinte dúvida:

"Gostaria de saber se é possível e como faço para o excel listar todas as combinações possíveis (sem repetições) compostas por 4 números de um conjunto de 62 números.

Isto é: eu tenho um conjunto de números que vai do 23 ao 80, mais o 87, o 88, o 90 e o 96.

Pretendo que o excel liste todas as combinações possíveis compostas por 4 números. Ex: 23-24-25-26, 23-24-26-25, 23-25-24-26, etc...O objectivo é, posteriormente, aplicar a formula (a/b)x(c/d) à listagem obtida.Obrigada"

É possível sim gerar combinações de números como essa. Primeiramente precisamos entender como o processo será feito.

Cada número precisará acontecer uma única vez na combinação, sem repetição. Para isso precisaremos de quatro estruturas de repetição (ou laços). Para ter todos os números em todas as quatro posições possíveis, precisaremos que todos os laços sejam do primeiro até o último número. Para evitar repetição, precisaremos conferir se o valor do número obtido é igual a um dos obtidos nos laços externos.

Desta forma, cada número será obtido no começo do laço e então será conferido se é igual a um dos outros laços (exceto no primeiro, por não haver necessidade). Somente no laço mais interno, após termos os quatro números, é que preencheremos os dados. Assim, teremos a seguinte estrutura idealizada:

    For Laco1 = 1 To [último valor]
        Valor1 = [dado]

        For Laco2 = 1 To [último valor]

            Valor2 = [dado]

            If Valor2 = Valor1 Then

                [pula para o próximo valor em Laco2]

            End If

            For Laco3 = 1 To [último valor]

                Valor3 = [dado]

                If Valor3 = Valor1 Or Valor3 = Valor2 Then

                    [pula para o próximo valor em Laco3]

                End If

                For Laco4 = 1 To [último valor]

                    Valor4 = [dado]

                    If Valor4 = Valor1 Or Valor4 = Valor2 Or Valor4 = Valor3 Then

                        [pula para o próximo valor em Laco4]

                    End If

                    [grava valores]

                Next Laco4

            Next Laco3

        Next Laco2

    Next Laco1

Entretanto, devemos observar que a quantidade de combinações a ser gerada é muito elevada. Se a combinação fosse de apenas três números, teríamos 61*60*59 combinações únicas (sem repetir um número na combinação), o que resulta em 215.940 combinações. Para adicionar mais um número à combinação, multiplicamos por 58 e obtemos 12.524.520, que é a quantidade de linhas que deverá ser gerada, muito acima dos 1.048.576 linhas que a planilha do Excel tem (e que muito julgam ser inalcançável).

Precisaremos então gerar uma "quebra de página". Podemos gerar essa quebra  quando chegar na última linha da planilha ou a cada uma determinada quantidade de valores do primeiro laço. Se optarmos pela primeira opção, teremos uma estrutura de verificação no laço mais interno (Laco4 acima) e será executada em todas as milhões de linha. Na segunda opção, a estrutura de verificação ficará no laço mais externo (Laco1 acima), que será executado nas 62 vezes que entrar no laço. Portanto, em termos de desempenho, a segunda opção será muito mais eficiente.

Como vamos estruturar essa quebra? Antes vamos definir onde irão ficar os números para gerar as combinações e as colunas com os dados resultantes. Vamos colocar os dados de origem na coluna A e por os números combinados nas colunas C, D, E e F, bem como a fórmula desejada na coluna G. Vamos manter uma linha de distância entre cada "bloco" de dados e começar a segunda "página" nas colunas I a M, a terceira nas colunas O a S e assim por diante. Ou seja, cada bloco começará 6 colunas adiante.

Vamos usar umas variáveis para auxiliar no posicionamento das colunas. Precisamos de apenas uma para a primeira coluna do bloco, as outras colunas podem usar este valor para posicionar. Como cada bloco está a 6 colunas de distância, então teremos de multiplicar a variável por 6. A posição inicial é a coluna C (terceira coluna), portanto temos de somar 3 à multiplicação. Porém, para que o primeiro bloco comece de fato na coluna C, é preciso inicializar o bloco com 0. Vamos à fórmula em código para compreender a ideia:

Posicao = Bloco * 6 + 3

Quando Bloco for 0, Posicao será 3, ou seja, coluna C. Quando Bloco for 1, Posicao será 9, que é a coluna I. E quando Bloco for 2, Posicao será 15, coluna O. Os blocos subsequentes seguirão sendo montados a cada 6 colunas. Portanto, esta fórmula resolve a questão do posicionamento da primeira coluna de cada bloco.

Já temos como gerar os blocos de dados. Falta criar a validação da quebra de bloco. Vamos fazer uma conta:

215.940 * 4 = 863.760
215.940 * 5 = 1.079.700 => passou das 1.048.576 linhas existentes em cada planilha do Excel.

Como vimos no cálculo acima, precisamos quebrar o bloco após 4 execuções para não passar do limite de linhas. Sabemos que um número é divisível por outro quando o resto é zero, portanto podemos usar esse método para dividir os blocos de 4 em 4. Veja o código:

If Laco1  Mod 4 = 0 Then

Assim, quando Laco1 for divisível por 4 será efetuada uma quebra. Porém, o laço começa em 1. Se analisarmos bem (fazendo teste de mesa), o primeiro bloco terá somente os três primeiros valores, enquanto o restante terá 4. Quando Laco1 for entre 1 e 3, os dados serão gravados no primeiro bloco, quando chegar a 4 vai pular para o segundo bloco. Para resolver isto subtraímos 1 de Laco1 um na verificação para começar a contagem no 0.

If (Laco1 - 1) Mod 4 = 0 Then

Agora sim, todos os blocos terão 4 números na primeira coluna. O posicionamento das colunas seguintes é fácil, Posicao + 1, Posicao + 2 etc.

Por fim, podemos melhorar o desempenho desabilitando o cálculo automático das fórmulas com a linha a seguir:

Application.Calculation = xlCalculationManual

Não esquecendo de habilitar depois ao término da execução:

Application.Calculation = xlCalculationAutomatic

Com toda a teoria devidamente explicada, é hora do código pronto:

Option Explicit
Sub FazerCombinacoes()

    Dim Quantidade As Integer
    Dim Linha As Long
    Dim Bloco As Long
    Dim Posicao As Long
    Dim Laco1 As Integer
    Dim Laco2 As Integer
    Dim Laco3 As Integer
    Dim Laco4 As Integer
    Dim Valor1 As Integer
    Dim Valor2 As Integer
    Dim Valor3 As Integer
    Dim Valor4 As Integer
    Application.Calculation = xlCalculationManual
    
    Quantidade = Range("A1:A62").Count
    Bloco = -1
    Linha = 1
    Posicao = 3

    For Laco1 = 1 To Quantidade
        If (Laco1 - 1) Mod 4 = 0 Then
            Bloco = Bloco + 1
            Linha = 1
            Posicao = Bloco * 6 + 3
            Debug.Print "Início do bloco " & (Bloco + 1) & ": " & Now
        End If
        Valor1 = Cells(Laco1, 1).Value
        For Laco2 = 1 To Quantidade
            Valor2 = Cells(Laco2, 1).Value
            If Valor2 = Valor1 Then
                GoTo SaiLaco2
            End If
            For Laco3 = 1 To Quantidade
                Valor3 = Cells(Laco3, 1).Value
                If Valor3 = Valor1 Or Valor3 = Valor2 Then
                    GoTo SaiLaco3
                End If
                For Laco4 = 1 To Quantidade
                    Valor4 = Cells(Laco4, 1).Value
                    If Valor4 = Valor1 Or Valor4 = Valor2 Or Valor4 = Valor3 Then
                        GoTo SaiLaco4
                    End If
                    Cells(Linha, Posicao).Value = Valor1
                    Cells(Linha, Posicao + 1).Value = Valor2
                    Cells(Linha, Posicao + 2).Value = Valor3
                    Cells(Linha, Posicao + 3).Value = Valor4
                    Cells(Linha, Posicao + 4).Formula = "=(" + _
                        Cells(Linha, Posicao).Address + "/" + _
                        Cells(Linha, Posicao + 1).Address + ")*(" + _
                        Cells(Linha, Posicao + 2).Address + "/" + _
                        Cells(Linha, Posicao + 3).Address + ")"
                    Linha = Linha + 1
                    Application.StatusBar = "Bloco: " & (Bloco + 1) & " / Linha: " & Linha
SaiLaco4:
                Next Laco4
                DoEvents
SaiLaco3:
            Next Laco3
SaiLaco2:
        Next Laco2
    Next Laco1

    Application.StatusBar = False
    Application.Calculation = xlCalculationAutomatic
    Debug.Print "Término do processamento: " & Now


End Sub

Observe que a variável Bloco foi inicializado com -1 para ficar com valor 0 na primeira execução do laço mais externo. Veja também que coloquei para mostrar o horário quando inicia cada bloco e quando termina o processamento, para ajudar a ter uma estimativa de quanto tempo leva para executar tudo. Esses horários serão exibidos na área Verificação imediata do editor VBA.

Perceba que o código está "engessado", sendo específico para o caso apresentado, envolvendo combinações de 4 números. Se precisar de combinações com mais ou menos números, será preciso adicionar ou remover laços e adaptar o código.

Para efetuar testes, sugiro que altere o intervalo para "A1:A10", por exemplo, para ter uma noção de quantas linhas são geradas e do funcionamento da rotina. No meu notebook, o processamento com 10 números levou menos de um minuto. A execução completa para todas as combinações de 62 números deve demorar muitas, muitas horas mesmo.

Pedro Martins

Formado em Tecnologia em Eletrônica Digital, já trabalhou como artefinalista, eletrotécnico, programador de CLP (para máquinas industriais) e analista de sistemas em sistema bancário, programando em COBOL.

Mexe com computadores e programação desde a segunda metade dos anos 1980, quando teve um MSX e aprendeu a programar em BASIC. É a favor da disseminação do conhecimento.