permutation.texi

This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY without ev

@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.
@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 (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}.
@end deftypefun

@node Reading and writing permutations
@section Reading and writing permutations

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

@deftypefun int gsl_permutation_fwrite (FILE * @var{stream}, const gsl_permutation * @var{p})
This function writes the elements of the permutation @var{p} to the
stream @var{stream} in binary format.  The function returns
@code{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.
@end deftypefun

@deftypefun int gsl_permutation_fread (FILE * @var{stream}, gsl_permutation * @var{p})
This function reads into the permutation @var{p} from the open stream
@var{stream} in binary format.  The permutation @var{p} must be
preallocated with the correct length since the function uses the size of
@var{p} to determine how many bytes to read.  The function returns
@code{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.
@end deftypefun

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

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

@node Permutations in cyclic form
@section Permutations in cyclic form

A permutation can be represented in both @dfn{linear} and @dfn{cyclic}
notations.  The functions described in this section convert between the
two forms.  The linear notation is an index mapping, and has already
been described above.  The cyclic notation expresses a permutation as a
series of circular rearrangements of groups of elements, or
@dfn{cycles}.

For example, under the cycle (1 2 3), 1 is replaced by 2, 2 is replaced
by 3 and 3 is replaced by 1 in a circular fashion. Cycles of different
sets of elements can be combined independently, for example (1 2 3) (4
5) combines the cycle (1 2 3) with the cycle (4 5), which is an exchange
of elements 4 and 5.  A cycle of length one represents an element which
is unchanged by the permutation and is referred to as a @dfn{singleton}.

It can be shown that every permutation can be decomposed into
combinations of cycles.  The decomposition is not unique, but can always
be rearranged into a standard @dfn{canonical form} by a reordering of
elements.  The library uses the canonical form defined in Knuth's
@cite{Art of Computer Programming} (Vol 1, 3rd Ed, 1997) Section 1.3.3,
p.178.

The procedure for obtaining the canonical form given by Knuth is,

@enumerate
@item Write all singleton cycles explicitly
@item Within each cycle, put the smallest number first
@item Order the cycles in decreasing order of the first number in the cycle.
@end enumerate

@noindent
For example, the linear representation (2 4 3 0 1) is represented as (1
4) (0 2 3) in canonical form. The permutation corresponds to an
exchange of elements 1 and 4, and rotation of elements 0, 2 and 3.

The important property of the canonical form is that it can be
reconstructed from the contents of each cycle without the brackets. In
addition, by removing the brackets it can be considered as a linear
representation of a different permutation. In the example given above
the permutation (2 4 3 0 1) would become (1 4 0 2 3).  This mapping has
many applications in the theory of permutations.

@deftypefun int gsl_permutation_linear_to_canonical (gsl_permutation * @var{q}, const gsl_permutation * @var{p})
This function computes the canonical form of the permutation @var{p} and
stores it in the output argument @var{q}.
@end deftypefun

@deftypefun int gsl_permutation_canonical_to_linear (gsl_permutation * @var{p}, const gsl_permutation * @var{q})
This function converts a permutation @var{q} in canonical form back into
linear form storing it in the output argument @var{p}.
@end deftypefun

@deftypefun size_t gsl_permutation_inversions (const gsl_permutation * @var{p})
This function counts the number of inversions in the permutation
@var{p}.  An inversion is any pair of elements that are not in order.
For example, the permutation 2031 has three inversions, corresponding to
the pairs (2,0) (2,1) and (3,1).  The identity permutation has no
inversions.
@end deftypefun

@deftypefun size_t gsl_permutation_linear_cycles (const gsl_permutation * @var{p})
This function counts the number of cycles in the permutation @var{p}, given in linear form.
@end deftypefun

@deftypefun size_t gsl_permutation_canonical_cycles (const gsl_permutation * @var{q})
This function counts the number of cycles in the permutation @var{q}, given in canonical form.
@end deftypefun


@node Permutation Examples
@section Examples
The example program below creates a random permutation (by shuffling the
elements of the identity) and finds its inverse.

@example
@verbatiminclude examples/permshuffle.c
@end example

@noindent
Here is the output from the program,

@example
$ ./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
@end example

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

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

@example
@verbatiminclude examples/permseq.c
@end example

@noindent
Here is the output from the program,

@example
$ ./a.out 
 0 1 2
 0 2 1
 1 0 2
 1 2 0
 2 0 1
 2 1 0
@end example

@noindent
The permutations are generated in lexicographic order.  To reverse the
sequence, begin with the final permutation (which is the reverse of the
identity) and replace @code{gsl_permutation_next} with
@code{gsl_permutation_prev}.

@node Permutation References and Further Reading
@section References and Further Reading

The subject of permutations is covered extensively in Knuth's
@cite{Sorting and Searching},

@itemize @asis
@item
Donald E. Knuth, @cite{The Art of Computer Programming: Sorting and
Searching} (Vol 3, 3rd Ed, 1997), Addison-Wesley, ISBN 0201896850.
@end itemize

@noindent
For the definition of the @dfn{canonical form} see,

@itemize @asis
@item
Donald E. Knuth, @cite{The Art of Computer Programming: Fundamental
Algorithms} (Vol 1, 3rd Ed, 1997), Addison-Wesley, ISBN 0201896850.
Section 1.3.3, @cite{An Unusual Correspondence}, p.178--179.
@end itemize