11 Multiconjuntos

Esse capítulo descreve funções para criar e manipular multiconjuntos. Um multiconjunto c é representado por um vetor estático de k inteiros no intervalo de 0 a n-1, onde cada valor c_i pode ocorrer mais de uma vez. O multiconjunto c corresponde a índices de k elementos escolhidos a partir de um vetor de n elementos com substituições. Em termos matemáticos, n é a cardinalidade do multiconjunto enquanto k é multiplicidade máxima de qualquer valor. Multiconjuntos são úteis, por exemplo, quando iteragindo sobre os índices de um tensor simétrico de k-ésima ordem no espaço de dimensão n.

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

11.1 A estrutura Multiconjunto

Um multiconjunto é definido por uma estrutura contendo três componentes, os valores de n e k, e um apontador para o vetor estático contendo os elementos do multiconjunto. Os elementos do vetor estático do multiconjunto são todos do tipo size_t, e são armazenados em ordem crescente. A estrutura gsl_multiset assemelha-se ao que segue,

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

11.2 Multiconjunto - alocação

Function: gsl_multiset * gsl_multiset_alloc (size_t n, size_t k)

Essa função aloca memória para um novo multiconjunto com parâmetros n, k. O multiconjunto não é inicializado e seus elementos são indefinidos. Use a função gsl_multiset_calloc se você deseja criar um multiconjunto que é inicializado para o primeiro multiconjunto elemento da ordem lexicográfica. Um apontador nulo é retornado se não hover memória suficiente para criar o multiconjunto.

Function: gsl_multiset * gsl_multiset_calloc (size_t n, size_t k)

Essa função aloca memória para um novo multiconjunto com parâmetros n, k e inicializa o conteúdo dessa memória para o primeiro multiconjunto elemento da ordem lexicográfica. Um apontador nulo é retornado se não houver memória suficiente para criar o multiconjunto.

Function: void gsl_multiset_init_first (gsl_multiset * c)

Essa função inicializa o multiconjunto c para o primeiro multiconjunto elementos da ordem lexicográfica, i.e. 0 repetido k vezes.

Function: void gsl_multiset_init_last (gsl_multiset * c)

Essa função inicializa o multiconjunto c para o último multiconjunto elemento da ordem lexicográfica, i.e. n-1 repetido k vezes.

Function: void gsl_multiset_free (gsl_multiset * c)

Essa função libera toda a memória usada pelo multiconjunto c.

Function: int gsl_multiset_memcpy (gsl_multiset * dest, const gsl_multiset * src)

Essa função copia os elementos do multiconjunto src para o multiconjunto dest. Os dois multiconjuntos devem ter o mesmo tamanho.

11.3 Acessando Elementos de Multiconjuntos

A seguinte função pode ser usada para acessar os elementos de um multiconjunto.

Function: size_t gsl_multiset_get (const gsl_multiset * c, const size_t i)

Essa função retorna o valor do i-ésimo elemento do multiconjunto c. Se i cair fora do intervalo permitido de 0 a k-1 então o menipulador de erro é chamado e 0 é retornado. Uma versão modificada dessa função é usada quando HAVE_INLINE for definida.

11.4 Multiconjuntos - propriedades

Function: size_t gsl_multiset_n (const gsl_multiset * c)

Essa função retorna o intervalo (n) do multiconjunto c.

Function: size_t gsl_multiset_k (const gsl_multiset * c)

Essa função retorna o número de elementos (k) no multiconjunto c.

Function: size_t * gsl_multiset_data (const gsl_multiset * c)

Essa função retorna um apontador para o vetor estático de elementos no multiconjunto c.

Function: int gsl_multiset_valid (gsl_multiset * c)

Essa função verifica se o multiconjunto c é válido. Os k elementos devem estar no intervalo de 0 a n-1, com cada valor ocorrendo ordem não decrescente.

11.5 funções de multiconjunto

Function: int gsl_multiset_next (gsl_multiset * c)

Essa função avança o multiconjunto c para o multiconjunto elemento seguinte na ordem lexicográfica e retorna GSL_SUCCESS. Se não houverem elementos multiconjuntos adicionais disponíveis a gsl_multiset_next retorna GSL_FAILURE e o multiconjunto elemento c permanece inalterado. Iniciando com o primeiro multiconjunto e repetidamente aplicando essa função irá ocorrer iteração através de todos os possíveis multiconjuntos de uma ordem fornecida.

Function: int gsl_multiset_prev (gsl_multiset * c)

Essa função retorna o multiconjunto c para o multiconjunto elemento anterior na ordem lexicográfica, retornando GSL_SUCCESS. Se não nenhum multiconjunto anterior disponível a gsl_multiset_prev retorna GSL_FAILURE e o multiconjunto elemento c permanece inalterado.

11.6 Multiconjuntos - Lendo e Escrevendo

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

Function: int gsl_multiset_fwrite (FILE * stream, const gsl_multiset * c)

Essa função escreve os elementos do multiconjunto c para o fluxo stream em formato binário. A função retorna GSL_EFAILED se houver um problema na escrita para o arquivo. Uma vez que os dados são escritos no formato binário nativo pode não ser portável entre diferentes arquiteturas.

Function: int gsl_multiset_fread (FILE * stream, gsl_multiset * c)

Essa função lê elementos a partir de fluxo aberto stream para o multiconjunto c em formato binário. O multiconjunto c deve ser pré-alocado com 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 de leitura a partir do arquivo. Os dados são assumidos terem sido escritos no formato binário nativo sobre a mesma arquitetura.

Function: int gsl_multiset_fprintf (FILE * stream, const gsl_multiset * c, const char * format)

Essa função escreve os elementos do multiconjunto c uma linha de cada vez para o fluxo stream usando o especificados 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.(31) A função retorna GSL_EFAILED se houver um problema de escrita para o arquivo.

Function: int gsl_multiset_fscanf (FILE * stream, gsl_multiset * c)

Essa função lê dados formatados a partir do fluxo stream para o multiconjunto c. O multiconjunto c deve ser pré-alocado 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 a partir do arquivo.

11.7 Exemplos

O programa exemplo abaixo imprime todos os multiconjuntos elementos contendo os valores {0,1,2,3} ordenados por tamanho. Elementos de multiconjuntos de mesmo tamanho são ordenados lexicograficamente.

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

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

  printf ("All multisets of {0,1,2,3} by size:\n") ;
  for (i = 0; i <= 4; i++)
    {
      c = gsl_multiset_calloc (4, i);
      do
        {
          printf ("{");
          gsl_multiset_fprintf (stdout, c, " %u");
          printf (" }\n");
        }
      while (gsl_multiset_next (c) == GSL_SUCCESS);
      gsl_multiset_free (c);
    }

  return 0;
}

Aqui está a saída do programa,

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

Todos os 70 multiconjuntos são gerados e ordenados lexicograficamente.

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