Dando continuidade à série sobre análise combinatória com SQL, este artigo aborda a combinação de elementos.
Introdução
“Considerando quatro funcionários de uma empresa (André, Bianca, Carlos e Dayse), quantas e quais são as equipes contendo 2 pessoas que podem ser formadas?”
Acima descrevemos um típico problema de análise combinatória envolvendo combinações de elementos de um conjunto. O conjunto em questão é formado por 4 elementos: os funcionários ‘André’, ‘Bianca’, ‘Carlos’ e ‘Dayse’, que, daqui em diante, representaremos pelas letras A, B, C e D, respectivamente. Para resolver o problema, devemos determinar todas as equipes possíveis, mas sem considerar as diferentes ordens dos elementos. Isso que dizer que quando trabalhamos com combinação {A, B} e {B, A} são considerados o mesmo conjunto, ao contrário do que ocorre quando trabalhamos com arranjos.
A resposta para a questão proposta no primeiro parágrafo é a seguinte: “AB”, “AC”, “AD”, “BC”, “BD”, “CD”
Neste exemplo, realizamos uma combinação de 4 elementos tomados 2 a 2. O total de equipes é 6. De uma maneira geral, uma combinação de n elementos r a r, representado por C(n,r) produz um total de n! / (r! x (n-r)!) subconjuntos. Em nosso exemplo: 4! / (2! (4-2)!) = 6.
Combinações com SQL
No artigo anterior, introduzimos um modelo composto por três regras para a construção de consultas SQL para a geração de arranjos em grupos de 2 elementos. Para gerarmos combinações via SQL, o modelo é bem parecido. As duas primeiras regras continuam iguais e a terceira é levemente modificada para evitar a geração de conjuntos com elementos iguais em ordens diferentes. O modelo do SQL para combinações é apresentado a seguir:
- Fazer o “self-join” da tabela-alvo (ou seja, instancia-la duas vezes), porém sem utilizar nenhuma condição de junção (sem ligar as duas instâncias da tabela por nenhum campo).
- Dar apelidos diferentes para cada uma das duas instâncias da tabela.
- Aplicar restrições na cláusula WHERE para evitar a produção de linhas contendo elementos iguais e ordens diferentes.
Como exemplo, considere a tabela T_CONJUNTO, cujo conteúdo é apresentado na Figura 1. Esta tabela possui apenas um campo, denominado ELEMENTO.
Figura 1: Tabela T_CONJUNTO
O SQL para realizar a combinação destes elementos 2 a 2 é apresentado abaixo. Veja que o “pulo do gato” - e a diferença em relação aos arranjos - consiste na utilização do operador “ < “ (“menor que”) na cláusula WHERE. Ele força com que em todas as tuplas retornadas, o elemento de T1 seja menor (tenha menor valor lexicográfico) do que o elemento de T2.
Listagem 1: Combinação de Elementos 2 a 2
SELECT * FROM T_CONJUNTO C1, T_CONJUNTO C2
WHERE C1.ELEMENTO < C2.ELEMENTO
O resultado é dado a seguir:
Figura 2: Resultado da Consulta - Combinação de elementos 2 a 2
Ordenando os Resultados
Assim como no caso dos arranjos, a cláusula ORDER BY pode ser utilizada para ordenar os resultados pelo (primeiro elemento prioritariamente, depois segundo elemento dos conjuntos).
Listagem 2: Arranjo dos Elementos 2 a 2 - Ordenando pelo Primeiro Elemento
SELECT * FROM T_CONJUNTO C1, T_CONJUNTO C2
WHERE C1.ELEMENTO < C2.ELEMENTO
ORDER BY C1.ELEMENTO, C2.ELEMENTO
Figura 3 Resultado da Consulta com ORDER BY
No próximo artigo, mostraremos que com SQL também podemos produzir arranjos e combinações 3 a 3, 4 a 4, etc. Até lá!
