10 Combinações

Esse capítulo descreve funções para criar e tratar combinações. Uma combinação c é representada por um vetor estático de k inteiros no intervalo de 0 a n-1, onde cada valor c_i ocorre no máximo uma vez. A combinação c corresponde a indices de k elementos escolhidos a partir de um vetor de n elementos. Combinações são úteis para iteragir sobre todos os k-elementos subconjuntos de um conjunto.

As funções descritas nesse capítulo estão definidas no arquivo de cabeçalho ‘gsl_combination.h’.

10.1 A Estrutura Combinação

Uma combinação é definida por uma estrutura contendo três componentes, os valores de n e k, e um apontador para o vetor estático de combinação. Os elementos do vetor de combinação são todos do tipo size_t, e são armazenados na ordem de incremento. A estrutura gsl_combination assemelha-se ao seguinte,

typedef struct
{
  size_t n;
  size_t k;
  size_t *data;
} gsl_combination;

10.2 Combinação - alocação

Function: gsl_combination * gsl_combination_alloc (size_t n, size_t k): Essa função aloca memória para uma nova combinação com parâmetros n, k. A combinação não é inicializada e seus elementos são indefinidos. Use a função gsl_combination_calloc se você deseja criar uma combinação que é inicializada para a primeira combinação lexicográfica. Um apontador null é retornado se não tiver memória suficiente para criar a combinação.

Function: gsl_combination * gsl_combination_calloc (size_t n, size_t k): Essa função aloca memória para uma nova combinação com parâmetros n, k e inicializa essa nova combinação para a primeira combinação lexicográfica. Um apontador nulo é retornado se não tiver memória suficiente para criar a combinação.

Function: void gsl_combination_init_first (gsl_combination * c): Essa função inicializa a combinação c para a primeira combinação lexicográfica, i.e. (0,1,2,…,k-1).

Function: void gsl_combination_init_last (gsl_combination * c): Essa função inicializa a combinação c para a última combinação lexicográfica, i.e. (n-k,n-k+1,…,n-1).

Function: void gsl_combination_free (gsl_combination * c): Essa função libera toda a memória usada pela combinação c.

Function: int gsl_combination_memcpy (gsl_combination * dest, const gsl_combination * src): Essa função copia os elementos da combinação src para a combinação dest. As duas combinações devem ter o mesmo tamanho.

10.3 Acessando elementos de uma combinação

A seguinte função pode ser usada para acessar os elementos de uma combinação.

Function: size_t gsl_combination_get (const gsl_combination * c, const size_t i): Essa função retorna o valor do i-ésimo elemento da combinação c. Se i cair fora do intervalo permitido de 0 a k-1 então o controlador de erro é chamado e 0 é retornado. Uma versão modificada dessa função é usada quando HAVE_INLINE for definida.

10.4 Combinação - propriedades

Function: size_t gsl_combination_n (const gsl_combination * c): Essa função retorna o intervalo (n) da combinação c.

Function: size_t gsl_combination_k (const gsl_combination * c): Essa função retorna o número de elementos (k) na combinação c.

Function: size_t * gsl_combination_data (const gsl_combination * c): Essa função retorna um apontador para o vetor estático de elementos na combinação c.

Function: int gsl_combination_valid (gsl_combination * c): Essa função verifica se a combinação c é válida. Os k elementos devem estar no intervalo de 0 a n-1, com cada valor ocorrendo no máximo uma vez e em ordem crescente.

10.5 Funções de Combinação

Function: int gsl_combination_next (gsl_combination * c): Essa função avança a combinação c para a combinação seguinte na ordem lexicográfica e retorna GSL_SUCCESS. Se nenhuma combinação adicional estiver disponível a gsl_combination_next retorna GSL_FAILURE e a combinação c permanece inalterada. Iniciando com a primeira combinação e repetidamente aplicando essa função irá iteragir através de todas as possíveis combinações de uma ordem fornecida.

Function: int gsl_combination_prev (gsl_combination * c): Essa função dá um passo atrás na combinação c no sentido da combinação anterior na ordem lexicográfica, retornando GSL_SUCCESS. Se nenhuma combinação anterior estiver disponível a gsl_combination_prev retorna GSL_FAILURE e a combinação c permanece inalterada.

10.6 Combinações - Lendo e Escrevendo

A biblioteca fornece funções de leitura e escrita de combinações para um arquivo tanto no formato binário quanto em texto formatado.

Function: int gsl_combination_fwrite (FILE * stream, const gsl_combination * c): Essa função escreve os elementos da combinação c para o fluxo stream em formato binário. A função retorna GSL_EFAILED se houver um problema de escrita para o arquivo. Uma vez que os dados são escritos no formato binário nativo pode não ser portável enrre diferentes arquiteturas.

Function: int gsl_combination_fread (FILE * stream, gsl_combination * c): Essa função lê elementos a partir de um fluxo aberto stream para a combinação c em formato binário. A combinação c deve ser pré-alocada com os valores corretos de n e k uma vez que a função utiliza o tamanho de c para determinar quantos bytes devem ser lidos. A função retorna GSL_EFAILED se houver um problema durante a leitura do arquivo. Os dados são assumidos terem sido escritos no formato binário nativo sobre a mesma arquitetura.

Function: int gsl_combination_fprintf (FILE * stream, const gsl_combination * c, const char * format): Essa função escreve os elementos da combinação c uma linha de cada vez para o fluxo stream usando o especificador de formato format, que deve ser adequado para o tipo size_t. No ISO C99 o modificador de tipo z representa size_t, de forma que "%zu\n" é um formato adequado.(30) A função retorna GSL_EFAILED se houver um problema de escrita para o arquivo.

Function: int gsl_combination_fscanf (FILE * stream, gsl_combination * c): Essa função lê dados formatados a partir do fluxo stream para a combinação c. A combinação c deve ser pré-alocada com valores corretos de n e k uma vez que a função usa o tamanho de c para determinar quantos números devem ser lidos. A função retorna GSL_EFAILED se houver um problema de leitura do arquivo.

10.7 Exemplos

O programa exemplo abaixo mostra na tela todos os subconjuntos do conjunto {0,1,2,3} ordenados por tamanho. Subconjuntos de mesmo tamanho são ordenados lexicográficamente.

#include <stdio.h>
#include <gsl/gsl_combination.h>

int 
main (void) 
{
  gsl_combination * c;
  size_t i;

  printf ("All subsets of {0,1,2,3} by size:\n") ;
  for (i = 0; i <= 4; i++)
    {
      c = gsl_combination_calloc (4, i);
      do
        {
          printf ("{");
          gsl_combination_fprintf (stdout, c, " %u");
          printf (" }\n");
        }
      while (gsl_combination_next (c) == GSL_SUCCESS);
      gsl_combination_free (c);
    }

  return 0;
}

Aqui está a saída do programa,

$ ./a.out 
All subsets of {0,1,2,3} by size:
{ }
{ 0 }
{ 1 }
{ 2 }
{ 3 }
{ 0 1 }
{ 0 2 }
{ 0 3 }
{ 1 2 }
{ 1 3 }
{ 2 3 }
{ 0 1 2 }
{ 0 1 3 }
{ 0 2 3 }
{ 1 2 3 }
{ 0 1 2 3 }

Todos os 16 subconjuntos são gerados, e os subconjuntos de cada tamanho são ordenados lexicograficamente.

10.8 Referências e Leituras Adicionais

Informações adicionais sobre combinações podem ser encontradas em,

Donald L. Kreher, Douglas R. Stinson, Combinatorial Algorithms: Generation, Enumeration and Search, 1998, CRC Press LLC, ISBN 084933988X

Esse documento foi gerado em 23 de Julho de 2013 usando texi2html 5.0.