9 Permutações

Esse capítulo descreve funções para criação e manipulação de permutações. Uma permutação p é representada por um vetor estático de n inteiros no intervalo de 0 a n-1, onde cada valor p_i ocorre uma vez e somente uma vez. A aplicação de uma permutação p a um vetor v retorna um novo vetor v' onde v'_i = v_{p_i}. Por exemplo, o vetor estático (0,1,3,2) representa uma permutação que troca de lugar os dois últimos elementos de um vetor de quatro elementos. A permutação identidade correspondente é (0,1,2,3).

Note que as permutações produzidas através de rotinas de álgebra linear correspondem à troca de lugar de colunas de matriz, e então deve ser considerada como aplicando a vetores linha na forma v' = v P em lugar de vetores coluna, quando permutando os elementos de um vetor.

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

9.1 A estrutura permutação

Uma permutação é definida através de uma estrutura contendo duas componentes, o tamanho da permutação e um apontador para o vetor estático de permutação. Os elementos do vetor estático de permutação são todos do tipo size_t. A estrutura gsl_permutation assemelha-se ao que segue adiante,

typedef struct
{
  size_t size;
  size_t * data;
} gsl_permutation;

9.2 Permutação - Alocação

Function: gsl_permutation * gsl_permutation_alloc (size_t n): Essa função aloca memória para uma nova permutação de tamanho n. A permutação não é inicializada e seus elementos são indefinidos. Use a função gsl_permutation_calloc se você deseja criar uma permutação que seja inicializada para a permutação identidade. Um apontador nulo é retornado se não tiver memória suficiente para criar a permutação.

Function: gsl_permutation * gsl_permutation_calloc (size_t n): Essa função aloca memória para uma nova permutação de tamanho n e inicializa essa nova permutação para a permutação identidade. Um apontador nulo é retornado se não tiver memória suficiente para criar a permutação.

Function: void gsl_permutation_init (gsl_permutation * p): Essa função inicializa a permutação p para a identidade, i.e. (0,1,2,…,n-1).

Function: void gsl_permutation_free (gsl_permutation * p): Essa função libera toda a memória usada pela permutação p.

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

9.3 Acessando elementos de uma permutação

As seguintes funções podem ser usadas para acessar e manipular permutações.

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

Function: int gsl_permutation_swap (gsl_permutation * p, const size_t i, const size_t j): Essa função intercambia o i-ésimo elemento pelo j-ésimo elemento da permutation p.

9.4 Permutação - propriedades

Function: size_t gsl_permutation_size (const gsl_permutation * p): Essa função retorna o tamanho da permutação p.

Function: size_t * gsl_permutation_data (const gsl_permutation * p): Essa função retorna um apontador para o vetor estático de elementos na permutação p.

Function: int gsl_permutation_valid (const gsl_permutation * p): Essa função verifica se a permutação p é válida. Os n elementos devem conter cada um dos números de 0 a n-1 uma vez e somente uma vez.

9.5 Funções de permutação

Function: void gsl_permutation_reverse (gsl_permutation * p): Essa função reverte os elementos da permutação p.

Function: int gsl_permutation_inverse (gsl_permutation * inv, const gsl_permutation * p): Essa função calcula a inversa da permutação p, armazenando o resultado em inv.

Function: int gsl_permutation_next (gsl_permutation * p): Essa função avança a permutação p para a permutação seguinte na ordem lexicográfica (28)e retorna GSL_SUCCESS. Se nenhuma permutação adicional estiver disponível a gsl_permutation_next retorna GSL_FAILURE e a permutação p fica inalterada. Iniciando com a permutação identidade e repetidamente aplicando essa função irá iteragir através de todas as possíveis permutações da ordem fornecida.

Function: int gsl_permutation_prev (gsl_permutation * p): Essa função retorna da permutação p para a permutação anterior em ordem lexicográfica, retornando GSL_SUCCESS. Se nenhuma permutação anterior estiver disponível a gsl_permutation_prev retorna GSL_FAILURE e a permutação p permanece inalterada.

9.6 Aplicando Permutações

Function: int gsl_permute (const size_t * p, double * data, size_t stride, size_t n): Essa função aplica a permutação p ao vetor estático data de tamanho n com salto stride.

Function: int gsl_permute_inverse (const size_t * p, double * data, size_t stride, size_t n): Essa função aplica a inversa da permutação p ao vetor estático data de tamanho n com salto stride.

Function: int gsl_permute_vector (const gsl_permutation * p, gsl_vector * v): Essa função aplica a permutação p aos elementos do vetor v, considerado como um vetor linha trabalhado sobre uma matriz de permutação pela direita, v' = v P. A j-ésima coluna da matriz de permutação P é fornecido pela p_j-ésima coluna da matriz identidade. A permutação p e o vetor v devem ter o mesmo comprimento.

Function: int gsl_permute_vector_inverse (const gsl_permutation * p, gsl_vector * v): Essa função aplica a inversa da permutação p aos elementos do vetor v, considerado como um vetor linha trabalhado sobre uma matrix de permutação inversa pela direita, v' = v P^T. Note que para matrizes de permutação a inversa é a mesma que a transposta. A j-ésima coluna da matriz de permutação P é fornecida pela p_j-ésima coluna da matriz identidade. A permutação p e o vetor v devem ter o mesmo comprimento.

Function: int gsl_permutation_mul (gsl_permutation * p, const gsl_permutation * pa, const gsl_permutation * pb): Essa função transforma duas permutações pa e pb em uma permutação única p, onde p = pa * pb. A permutação p é equivalente a aplicar a permutação pb primeiramente e a seguir a permutação pa.

9.7 Permutações - Lendo e Escrevendo

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

Function: int gsl_permutation_fwrite (FILE * stream, const gsl_permutation * p): Essa função escreve os elementos da permutação p no fluxo stream em formato binário. A função retorna GSL_EFAILED se houver um problema durante a escrita para o arquivo. Uma vez que os dados são escritos no formato binário esses mesmos dados podem não serem portáveis entre as diferentes arquiteturas.

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

Function: int gsl_permutation_fprintf (FILE * stream, const gsl_permutation * p, const char * format): Essa função escreve os elementos da permutação p uma linha de cada vez para o fluxo stream usando o especificador de formato format, que deve ser ajustado para o tipo size_t. No ISO C99 o modificador de tipo z representa size_t, de forma que "%zu\n" é um formato adequado.(29) A função retorna GSL_EFAILED se houver um problema writing to the file.

Function: int gsl_permutation_fscanf (FILE * stream, gsl_permutation * p): Essa função lê dados formatados a partir do fluxo stream para dentro da permutação p. A permutação p deve ser pré-alocada com o correto número de elementos uma vez que a função utiliza o tamanho de p para determinar quantos números ler. A função retorna GSL_EFAILED se houver um problema de leitura do arquivo.

9.8 Permutações Cíclicas

A permutação pode ser representada em ambas as notações linear e ciclica. As funções descritas nessa seção convertem de uma das formas para a outra. A notação linear é um mapeamento de índices, e já foi descrita acima. A notação cíclica expressa uma permutação como uma serie de rearranjos circulares de grupos de elementos, ou ciclos.

Por exemplo, sob o ciclo (1 2 3), 1 é substituído por 2, 2 é substituído por 3 e 3 é substituído por um em um caminho circular. Ciclos de diferentes conjuntos de elementos podem ser combinados independentemente, por exemplo (1 2 3) (4 5) combina o ciclo (1 2 3) com o ciclo (4 5), que é uma troca de lugar dos elementos 4 e 5. Um ciclo de comprimento 1 representa um elemento que permanece inalterado pela permutação e é referenciado como unitário.

Pode ser mostrado que todas permutação pode ser decomposta em combinações de ciclos. A decomposição não é única, mas pode sempre ser rearranjada em uma forma canônica padrão por meio de uma reordenação de elementos. A biblioteca usa a forma canônica definida em Knuth Art of Computer Programming (Vol 1, 3a Ed, 1997) Seção 1.3.3, p.178.

O procedimento para obter a forma canônica fornecido em Knuth é,

Escreva todos os ciclos unitários explicitamente
Dentro de cada ciclo, coloque o menor número primeiro
Ordene os ciclos em ordem decrescente do primeiro número no ciclo.

Por exemplo, a representação linear (2 4 3 0 1) é representado com (1 4) (0 2 3) na forma canônica. A permutação corresponde a uma troca dos elementos 1 e 4, e rotação dos elementos 0, 2 e 3.

A propriedade importante da forma canônica é que a forma canônica pode ser reconstruída a partir do conteúdo de cada ciclo sem os parêntesis. Adicionalmente, através da remoção dos parêntesis a forma canônica pode ser considerada como uma representação linear de uma permutação diferente. No exemplo fornecido acima a permutação (2 4 3 0 1) pode tornar-se (1 4 0 2 3). Esse mapeamento tem muitas aplicações na teoria das permutações.

Function: int gsl_permutation_linear_to_canonical (gsl_permutation * q, const gsl_permutation * p): Essa função encontra a forma canônica da permutação p e armazena essa forma canônica encontrada no argumento de saída q.

Function: int gsl_permutation_canonical_to_linear (gsl_permutation * p, const gsl_permutation * q): Essa função converte uma permutação q na forma canônica de volta para a forma linear armazenando essa forma linear no argumento de saída p.

Function: size_t gsl_permutation_inversions (const gsl_permutation * p): Essa função conta o número de inversões na permutação p. Uma inversão é um par de elementos que não estão em ordem. Por exemplo, a permutação 2031 tem três inversões, correspondendo aos pares (2,0) (2,1) e (3,1). A permutação identidade não tem inversões.

Function: size_t gsl_permutation_linear_cycles (const gsl_permutation * p): Essa função conta o número de ciclos na permutação p, fornecido na forma linear.

Function: size_t gsl_permutation_canonical_cycles (const gsl_permutation * q): Essa função conta o número de ciclos na permutação q, fornecendo na forma canônica.

9.9 Exemplos

O programa exemplo adiante cria uma permutação aleatória (misturando os elementos da identidade) e encontra sua inversa.

#include <stdio.h>
#include <gsl/gsl_rng.h>
#include <gsl/gsl_randist.h>
#include <gsl/gsl_permutation.h>

int
main (void) 
{
  const size_t N = 10;
  const gsl_rng_type * T;
  gsl_rng * r;

  gsl_permutation * p = gsl_permutation_alloc (N);
  gsl_permutation * q = gsl_permutation_alloc (N);

  gsl_rng_env_setup();
  T = gsl_rng_default;
  r = gsl_rng_alloc (T);

  printf ("initial permutation:");  
  gsl_permutation_init (p);
  gsl_permutation_fprintf (stdout, p, " %u");
  printf ("\n");

  printf (" random permutation:");  
  gsl_ran_shuffle (r, p->data, N, sizeof(size_t));
  gsl_permutation_fprintf (stdout, p, " %u");
  printf ("\n");

  printf ("inverse permutation:");  
  gsl_permutation_inverse (q, p);
  gsl_permutation_fprintf (stdout, q, " %u");
  printf ("\n");

  gsl_permutation_free (p);
  gsl_permutation_free (q);
  gsl_rng_free (r);

  return 0;
}

Aqui está a saída do programa,

$ ./a.out 
initial permutation: 0 1 2 3 4 5 6 7 8 9
 random permutation: 1 3 5 2 7 6 0 4 9 8
inverse permutation: 6 0 3 1 7 2 5 4 9 8

A permutação aleatória p[i] e sua inversa q[i] são relacionadas através da identidade p[q[i]] = i, que pode ser verificada a partir da saída.

O próximo programa exemplo dá mais alguns passos adiante de todas as possíveis permutações de terceira ordem, iniciando a partir da identidade,

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

int
main (void) 
{
  gsl_permutation * p = gsl_permutation_alloc (3);

  gsl_permutation_init (p);

  do 
   {
      gsl_permutation_fprintf (stdout, p, " %u");
      printf ("\n");
   }
  while (gsl_permutation_next(p) == GSL_SUCCESS);

  gsl_permutation_free (p);

  return 0;
}

Aqui está a saída do programa,

As permutações são geradas na ordem lexicográfica. Para reverter a sequência, iniciando com a permutação final (que é a inversa da identidade) substitua gsl_permutation_next por gsl_permutation_prev.

9.10 Referências e Leituras Adicionais

O assunto permutações é abrangido extensivamente por Knuth em Sorting and Searching,

Donald E. Knuth, The Art of Computer Programming: Sorting and Searching (Vol 3, 3rd Ed, 1997), Addison-Wesley, ISBN 0201896850.

Para a definição da forma canônica veja,

Donald E. Knuth, The Art of Computer Programming: Fundamental Algorithms (Vol 1, 3rd Ed, 1997), Addison-Wesley, ISBN 0201896850. Section 1.3.3, An Unusual Correspondence, p.178–179.

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