Go to the first, previous, next, last section, table of contents.


Permutations

This chapter describes functions for creating and manipulating permutations. A permutation p is represented by an array of n integers in the range 0 .. n-1, where each value p_i occurs once and only once. The application of a permutation p to a vector v yields a new vector v' where v'_i = v_{p_i}. For example, the array (0,1,3,2) represents a permutation which exchanges the last two elements of a four element vector. The corresponding identity permutation is (0,1,2,3).

The functions described in this chapter are defined in the header file `gsl_permutation.h'.

The Permutation struct

A permutation is stored by a structure containing two members, the size of the permutation and a pointer to the permutation array. The elements of the permutation array are all of type size_t. The gsl_permutation structure looks like this,

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

Permutation allocation

Function: gsl_permutation * gsl_permutation_alloc (size_t n)
This function allocates memory for a new permutation of size n. The permutation is not initialized and its elements are undefined. Use the function gsl_permutation_calloc if you want to create a permutation which is initialized to the identity. A null pointer is returned if insufficient memory is available to create the permutation.

Function: gsl_permutation * gsl_permutation_calloc (size_t n)
This function allocates memory for a new permutation of size n and initializes it to the identity. A null pointer is returned if insufficient memory is available to create the permutation.

Function: void gsl_permutation_init (gsl_permutation * p)
This function initializes the permutation p to the identity, i.e. (0,1,2,...,n-1).

Function: void gsl_permutation_free (gsl_permutation * p)
This function frees all the memory used by the permutation p.

Accessing permutation elements

The following functions can be used to access and manipulate permutations.

Function: size_t gsl_permutation_get (const gsl_permutation * p, const size_t i)
This function returns the value of the i-th element of the permutation p. If i lies outside the allowed range of 0 to n-1 then the error handler is invoked and 0 is returned.

Function: int gsl_permutation_swap (gsl_permutation * p, const size_t i, const size_t j)
This function exchanges the i-th and j-th elements of the permutation p.

Permutation properties

Function: size_t gsl_permutation_size (const gsl_permutation * p)
This function returns the size of the permutation p.

Function: size_t * gsl_permutation_data (const gsl_permutation * p)
This function returns a pointer to the array of elements in the permutation p.

Function: int gsl_permutation_valid (gsl_permutation * p)
This function checks that the permutation p is valid. The n elements should contain each of the numbers 0 .. n-1 once and only once.

Permutation functions

Function: void gsl_permutation_reverse (gsl_permutation * p)
This function reverses the elements of the permutation p.

Function: int gsl_permutation_inverse (gsl_permutation * inv, const gsl_permutation * p)
This function computes the inverse of the permuation p, storing the result in inv.

Function: int gsl_permutation_next (gsl_permutation * p)
This function advances the permutation p to the next permutation in lexicographic order and returns GSL_SUCCESS. If no further permutations are available it returns GSL_FAILURE and leaves p unmodified. Starting with the identity permutation and repeatedly applying this function will iterate through all possible permutations of a given order.

Function: int gsl_permutation_prev (gsl_permutation * p)
This function steps backwards from the permutation p to the previous permutation in lexicographic order, returning GSL_SUCCESS. If no previous permutation is available it returns GSL_FAILURE and leaves p unmodified.

Applying Permutations

Function: int gsl_permute (const size_t * p, double * data, size_t stride, size_t n)
This function applies the permutation p to the array data of size n with stride stride.

Function: int gsl_permute_inverse (const size_t * p, double * data, size_t stride, size_t n)
This function applies the inverse of the permutation p to the array data of size n with stride stride.

Function: int gsl_permute_vector (const gsl_permutation * p, gsl_vector * v)
This function applies the permutation p to the elements of the vector v. The permutation p and the vector v must have the same length.

Function: int gsl_permute_vector_inverse (const gsl_permutation * p, gsl_vector * v)
This function applies the inverse of the permutation p to the elements of the vector v. The permutation p and the vector v must have

Reading and writing permutations

The library provides functions for reading and writing permutations to a file as binary data or formatted text.

Function: int gsl_permutation_fwrite (FILE * stream, const gsl_permutation * p)
This function writes the elements of the permutation p to the stream stream in binary format. The function returns GSL_EFAILED if there was a problem writing to the file. Since the data is written in the native binary format it may not be portable between different architectures.

Function: int gsl_permutation_fread (FILE * stream, gsl_permutation * p)
This function reads into the permutation p from the open stream stream in binary format. The permutation p must be preallocated with the correct length since the function uses the size of p to determine how many bytes to read. The function returns GSL_EFAILED if there was a problem reading from the file. The data is assumed to have been written in the native binary format on the same architecture.

Function: int gsl_permutation_fprintf (FILE * stream, const gsl_permutation * p, const char *format)
This function writes the elements of the permutation p line-by-line to the stream stream using the format specifier format, which should be suitable for a type of size_t. On a GNU system the type modifier Z represents size_t, so "%Zu\n" is a suitable format. The function returns GSL_EFAILED if there was a problem writing to the file.

Function: int gsl_permutation_fscanf (FILE * stream, gsl_permutation * p)
This function reads formatted data from the stream stream into the permutation p. The permutation p must be preallocated with the correct length since the function uses the size of p to determine how many numbers to read. The function returns GSL_EFAILED if there was a problem reading from the file.

Examples

The example program below creates a random permutation by shuffling and finds its inverse.

#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 ;
  gsl_rng * r = gsl_rng_alloc (gsl_rng_env_setup()) ;

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

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

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

  printf("inverse permutation:") ;  
  gsl_permutation_invert (p_inv, p);
  gsl_permutation_fprintf (stdout, p_inv, " %u") ;
  printf("\n") ;
}

Here is the output from the program,

bash$ ./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

The random permutation p[i] and its inverse q[i] are related through the identity p[q[i]] = i, which can be verified from the output.

The next example program steps forwards through all possible 3-rd order permutations, starting from the identity,

#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);
}

Here is the output from the program,

bash$ ./a.out 
 0 1 2
 0 2 1
 1 0 2
 1 2 0
 2 0 1
 2 1 0

All 6 permutations are generated in lexicographic order. To reverse the sequence, begin with the final permutation (which is the reverse of the identity) and replace gsl_permutation_next with gsl_permutation_prev.

References and Further Reading

The subject of permutations is covered extensively in Knuth's Sorting and Searching,


Go to the first, previous, next, last section, table of contents.