permutation.texi

math library from gnu

@cindex permutations

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

Note that the permutations produced by the linear algebra routines
correspond to the exchange of matrix columns, and so should be considered
as applying to row-vectors in the form @math{v' = v P} rather than
column-vectors, when permuting the elements of a vector.

The functions described in this chapter are defined in the header file
@file{gsl_permutation.h}.

@menu
* The Permutation struct::      
* Permutation allocation::      
* Accessing permutation elements::  
* Permutation properties::      
* Permutation functions::       
* Applying Permutations::       
* Reading and writing permutations::  
* Permutations in cyclic form::  
* Permutation Examples::        
* Permutation References and Further Reading::  
@end menu

@node The Permutation struct
@section The Permutation struct

A permutation is defined by a structure containing two components, the size
of the permutation and a pointer to the permutation array.  The elements
of the permutation array are all of type @code{size_t}.  The
@code{gsl_permutation} structure looks like this,

@example
typedef struct
@{
  size_t size;
  size_t * data;
@} gsl_permutation;
@end example
@comment

@noindent

@node Permutation allocation
@section Permutation allocation

@deftypefun {gsl_permutation *} gsl_permutation_alloc (size_t @var{n})
This function allocates memory for a new permutation of size @var{n}.
The permutation is not initialized and its elements are undefined.  Use
the function @code{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.
@end deftypefun

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

@deftypefun void gsl_permutation_init (gsl_permutation * @var{p})
@cindex identity permutation
This function initializes the permutation @var{p} to the identity, i.e.
@math{(0,1,2,@dots{},n-1)}.
@end deftypefun

@deftypefun void gsl_permutation_free (gsl_permutation * @var{p})
This function frees all the memory used by the permutation @var{p}.
@end deftypefun

@deftypefun int gsl_permutation_memcpy (gsl_permutation * @var{dest}, const gsl_permutation * @var{src})
This function copies the elements of the permutation @var{src} into the
permutation @var{dest}.  The two permutations must have the same size.
@end deftypefun

@node Accessing permutation elements
@section Accessing permutation elements

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

@deftypefun size_t gsl_permutation_get (const gsl_permutation * @var{p}, const size_t @var{i})
This function returns the value of the @var{i}-th element of the
permutation @var{p}.  If @var{i} lies outside the allowed range of 0 to
@math{@var{n}-1} then the error handler is invoked and 0 is returned.  @inlinefn{}
@end deftypefun

@deftypefun int gsl_permutation_swap (gsl_permutation * @var{p}, const size_t @var{i}, const size_t @var{j})
@cindex exchanging permutation elements
@cindex swapping permutation elements
This function exchanges the @var{i}-th and @var{j}-th elements of the
permutation @var{p}.
@end deftypefun

@node Permutation properties
@section Permutation properties

@deftypefun size_t gsl_permutation_size (const gsl_permutation * @var{p})
This function returns the size of the permutation @var{p}.
@end deftypefun

@deftypefun {size_t *} gsl_permutation_data (const gsl_permutation * @var{p})
This function returns a pointer to the array of elements in the
permutation @var{p}.
@end deftypefun

@deftypefun int gsl_permutation_valid (const gsl_permutation * @var{p})
@cindex checking permutation for validity
@cindex testing permutation for validity
This function checks that the permutation @var{p} is valid.  The @var{n}
elements should contain each of the numbers 0 to @math{@var{n}-1} once and only
once.
@end deftypefun

@node Permutation functions
@section Permutation functions

@deftypefun void gsl_permutation_reverse (gsl_permutation * @var{p})
@cindex reversing a permutation
This function reverses the elements of the permutation @var{p}.
@end deftypefun

@deftypefun int gsl_permutation_inverse (gsl_permutation * @var{inv}, const gsl_permutation * @var{p})
@cindex inverting a permutation
This function computes the inverse of the permutation @var{p}, storing
the result in @var{inv}.
@end deftypefun

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

@deftypefun int gsl_permutation_prev (gsl_permutation * @var{p})
This function steps backwards from the permutation @var{p} to the
previous permutation in lexicographic order, returning
@code{GSL_SUCCESS}.  If no previous permutation is available it returns
@code{GSL_FAILURE} and leaves @var{p} unmodified.
@end deftypefun

@node Applying Permutations
@section Applying Permutations

@deftypefun int gsl_permute (const size_t * @var{p}, double * @var{data}, size_t @var{stride}, size_t @var{n})
This function applies the permutation @var{p} to the array @var{data} of
size @var{n} with stride @var{stride}.
@end deftypefun

@deftypefun int gsl_permute_inverse (const size_t * @var{p}, double * @var{data}, size_t @var{stride}, size_t @var{n})
This function applies the inverse of the permutation @var{p} to the
array @var{data} of size @var{n} with stride @var{stride}.
@end deftypefun

@deftypefun int gsl_permute_vector (const gsl_permutation * @var{p}, gsl_vector * @var{v})
This function applies the permutation @var{p} to the elements of the
vector @var{v}, considered as a row-vector acted on by a permutation
matrix from the right, @math{v' = v P}.  The @math{j}-th column of the
permutation matrix @math{P} is given by the @math{p_j}-th column of the
identity matrix. The permutation @var{p} and the vector @var{v} must
have the same length.
@end deftypefun

@deftypefun int gsl_permute_vector_inverse (const gsl_permutation * @var{p}, gsl_vector * @var{v})
This function applies the inverse of the permutation @var{p} to the
elements of the vector @var{v}, considered as a row-vector acted on by
an inverse permutation matrix from the right, @math{v' = v P^T}.  Note
that for permutation matrices the inverse is the same as the transpose.
The @math{j}-th column of the permutation matrix @math{P} is given by
the @math{p_j}-th column of the identity matrix. The permutation @var{p}
and the vector @var{v} must have the same length.
@end deftypefun

@deftypefun int gsl_permutation_mul (gsl_permutation * @var{p}, const gsl_permutation * @var{pa}, const gsl_permutation * @var{pb})
This function combines the two permutations @var{pa} and @var{pb} into a
single permutation @var{p}, where @math{p = pa . pb}. The permutation
@var{p} is equivalent to applying @math{pb} first and then @var{pa}.