Go to the first, previous, next, last section, table of contents.
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'.
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 ;
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.
The following functions can be used to access and manipulate permutations.
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.
GSL_SUCCESS. If no previous permutation is available it returns
GSL_FAILURE and leaves p unmodified.
The library provides functions for reading and writing permutations to a file as binary data or formatted text.
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.
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.
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.
GSL_EFAILED if there was a problem reading from the file.
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.
The subject of permutations is covered extensively in Knuth's Sorting and Searching,
Go to the first, previous, next, last section, table of contents.