Combinações em C++ – Uma abordagem elementar

A análise combinatória é um ramo da matemética que, de uma forma pouco rigorosa, podemos afirmar que se dedica ao estudo da forma como podemos organizar coleções de objetos, com especial enfoque na sua contagem.

Por exemplo, se considerarmos as moedas em circulação em Portugal temos:

moedas

Imaginemos agora que pretendemos, dispondo de quantidades infinitas de cada tipo de moeda, calcular as possibilidades de determinar o valor de qualquer conjunto de quatro moedas possível.

Por questões de simplificação, vamos considerar os valores em cêntimos.

Vamos separar a nossa análise em dois grupos:

  1. com repetição – podemos repetir moedas iguais.
  2. sem repetição – não podemos repetir moedas iguais.

1. Fazer grupos de quatro moedas com repetição

Numa primeira abordagem, podemos começar a registar, de forma organizada, todas as possibilidades:

1 1 1 1

1 1 1 2

1 1 1 5

1 1 1 10

Obviamente que já deu para reparar que, seguindo este método manualmente, vamos demorar muito tempo a obter todas as possibilidades.

Uma vez que pretendemos determinar os subconjuntos de 4 moedas (r=4), de entre o conjunto das moedas em circulação (n=8), vamos recorrer àquilo que em análise combinatória se designa por “Arranjos com Repetição”.

Recorrendo a esta expressão, no nosso caso teremos 4096 possibilidades diferentes.

Uma forma muito simples de percorrer todas as combinações possíveis será o recurso ao ciclo for. Como pretendemos obter arranjos de 4 moedas, utilizaremos quatro destes ciclos encadeados.

#include <iostream>
using namespace std;
int main()
{
    int n = 8;
    int moedas[8] = {1, 2, 5, 10, 20, 50, 100, 200};
    int l0, l1, l2, l3;
    int total = 0;

    for (l0=0; l0<n; l0++)
    {
        for (l1=0; l1<n; l1++)
        {
            for (l2=0; l2<n;l2++)
            {
                for (l3=0; l3<n;l3++)
                {
                    cout << moedas[l0] << " " << moedas[l1] << " " << moedas[l2] << " " << moedas[l3] << endl;
                    total++;
                }
            }
        }
    }
    cout << total << endl;
    return 0;
}

2. Fazer grupos de quatro moedas sem repetição

Procedendo de forma semelhante temos:

1 2 5 10

1 2 5 20

1 10 5 50

1 10 5 100

Mesmo eliminando os conjuntos em que se repetiam moedas, continua a ser um processo complexo e demorado.

Na realidade a ordem por que são selecionadas as moedas não é importante uma vez que o subconjunto 1 2 5 10 é exatamente o mesmo que 2 1 10 5.

Nesta situação vamos recorrer ao cálculo de combinações simples, cuja expressão é a seguinte.

Aplicando os nossos valores a exta expressão obtemos 70 possibilidades.

Vamos obter o resultado pretendido, realizando algumas pequenas alterações no algoritmo anterior.

#include <iostream>
using namespace std;
int main()
{
    int n = 8;
    int moedas[8] = {1, 2, 5, 10, 20, 50, 100, 200};
    int l0, l1, l2, l3;
    int total = 0;

    for (l0=0; l0<n-3; l0++)
    {
        for (l1=l0+1; l1<n-2; l1++)
        {
            for (l2=l1+1; l2<n-1;l2++)
            {
                for (l3=l2+1; l3<n;l3++)
                {
                    cout << moedas[l0] << " " << moedas[l1] << " " << moedas[l2] << " " << moedas[l3] << endl;
                    total++;
                }
            }
        }
    }
    cout << total << endl;
    return 0;
}

Observações

Este código pode ser facilmente adaptável a outras situações.

Por exemplo, se pretendermos obter o mesmo resultado para conjuntos de 5 moedas, bastaria acrescentar mais um ciclo for, com as respetivas adaptações.

Da mesma forma, basta alterar o valor de n para, rapidamente, tratar conjuntos de diferentes dimensões.

Por outro lado, trata-se de uma solução pouco escalável, e o facto de estar dependente de alterações no código torna-a pouco eficiente. No entanto, se necessitarmos de realizar esta tarefa com conjuntos de dimensão reduzida, é uma hipótese a considerar.

Anúncios

One thought on “Combinações em C++ – Uma abordagem elementar

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão / Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão / Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão / Alterar )

Google+ photo

Está a comentar usando a sua conta Google+ Terminar Sessão / Alterar )

Connecting to %s