|
Packit |
67cb25 |
.. index:: permutations
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
************
|
|
Packit |
67cb25 |
Permutations
|
|
Packit |
67cb25 |
************
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. include:: include.rst
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This chapter describes functions for creating and manipulating
|
|
Packit |
67cb25 |
permutations. A permutation :math:`p` is represented by an array of
|
|
Packit |
67cb25 |
:math:`n` integers in the range 0 to :math:`n-1`, where each value
|
|
Packit |
67cb25 |
:math:`p_i` occurs once and only once. The application of a permutation
|
|
Packit |
67cb25 |
:math:`p` to a vector :math:`v` yields a new vector :math:`v'` where
|
|
Packit |
67cb25 |
:math:`v'_i = v_{p_i}`.
|
|
Packit |
67cb25 |
For example, the array :math:`(0,1,3,2)` represents a permutation
|
|
Packit |
67cb25 |
which exchanges the last two elements of a four element vector.
|
|
Packit |
67cb25 |
The corresponding identity permutation is :math:`(0,1,2,3)`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Note that the permutations produced by the linear algebra routines
|
|
Packit |
67cb25 |
correspond to the exchange of matrix columns, and so should be considered
|
|
Packit |
67cb25 |
as applying to row-vectors in the form :math:`v' = v P` rather than
|
|
Packit |
67cb25 |
column-vectors, when permuting the elements of a vector.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The functions described in this chapter are defined in the header file
|
|
Packit |
67cb25 |
:file:`gsl_permutation.h`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The Permutation struct
|
|
Packit |
67cb25 |
======================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. type:: gsl_permutation
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
A permutation is defined by a structure containing two components, the size
|
|
Packit |
67cb25 |
of the permutation and a pointer to the permutation array. The elements
|
|
Packit |
67cb25 |
of the permutation array are all of type :code:`size_t`. The
|
|
Packit |
67cb25 |
:type:`gsl_permutation` structure looks like this::
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
typedef struct
|
|
Packit |
67cb25 |
{
|
|
Packit |
67cb25 |
size_t size;
|
|
Packit |
67cb25 |
size_t * data;
|
|
Packit |
67cb25 |
} gsl_permutation;
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Permutation allocation
|
|
Packit |
67cb25 |
======================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: gsl_permutation * gsl_permutation_alloc (size_t n)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function allocates memory for a new permutation of size :data:`n`.
|
|
Packit |
67cb25 |
The permutation is not initialized and its elements are undefined. Use
|
|
Packit |
67cb25 |
the function :func:`gsl_permutation_calloc` if you want to create a
|
|
Packit |
67cb25 |
permutation which is initialized to the identity. A null pointer is
|
|
Packit |
67cb25 |
returned if insufficient memory is available to create the permutation.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: gsl_permutation * gsl_permutation_calloc (size_t n)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function allocates memory for a new permutation of size :data:`n` and
|
|
Packit |
67cb25 |
initializes it to the identity. A null pointer is returned if
|
|
Packit |
67cb25 |
insufficient memory is available to create the permutation.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index:: identity permutation
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: void gsl_permutation_init (gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function initializes the permutation :data:`p` to the identity, i.e.
|
|
Packit |
67cb25 |
:math:`(0, 1, 2, \dots, n - 1)`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: void gsl_permutation_free (gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function frees all the memory used by the permutation :data:`p`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_memcpy (gsl_permutation * dest, const gsl_permutation * src)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function copies the elements of the permutation :data:`src` into the
|
|
Packit |
67cb25 |
permutation :data:`dest`. The two permutations must have the same size.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Accessing permutation elements
|
|
Packit |
67cb25 |
==============================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The following functions can be used to access and manipulate
|
|
Packit |
67cb25 |
permutations.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: size_t gsl_permutation_get (const gsl_permutation * p, const size_t i)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function returns the value of the :data:`i`-th element of the
|
|
Packit |
67cb25 |
permutation :data:`p`. If :data:`i` lies outside the allowed range of 0 to
|
|
Packit |
67cb25 |
:math:`n - 1` then the error handler is invoked and 0 is returned. |inlinefn|
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: exchanging permutation elements
|
|
Packit |
67cb25 |
single: swapping permutation elements
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_swap (gsl_permutation * p, const size_t i, const size_t j)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function exchanges the :data:`i`-th and :data:`j`-th elements of the
|
|
Packit |
67cb25 |
permutation :data:`p`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Permutation properties
|
|
Packit |
67cb25 |
======================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: size_t gsl_permutation_size (const gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function returns the size of the permutation :data:`p`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: size_t * gsl_permutation_data (const gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function returns a pointer to the array of elements in the
|
|
Packit |
67cb25 |
permutation :data:`p`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index::
|
|
Packit |
67cb25 |
single: checking permutation for validity
|
|
Packit |
67cb25 |
single: testing permutation for validity
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_valid (const gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function checks that the permutation :data:`p` is valid. The :code:`n`
|
|
Packit |
67cb25 |
elements should contain each of the numbers 0 to :code:`n - 1` once and only
|
|
Packit |
67cb25 |
once.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Permutation functions
|
|
Packit |
67cb25 |
=====================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index:: reversing a permutation
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: void gsl_permutation_reverse (gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function reverses the elements of the permutation :data:`p`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index:: inverting a permutation
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_inverse (gsl_permutation * inv, const gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function computes the inverse of the permutation :data:`p`, storing
|
|
Packit |
67cb25 |
the result in :data:`inv`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. index:: iterating through permutations
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_next (gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function advances the permutation :data:`p` to the next permutation
|
|
Packit |
67cb25 |
in lexicographic order and returns :macro:`GSL_SUCCESS`. If no further
|
|
Packit |
67cb25 |
permutations are available it returns :macro:`GSL_FAILURE` and leaves
|
|
Packit |
67cb25 |
:data:`p` unmodified. Starting with the identity permutation and
|
|
Packit |
67cb25 |
repeatedly applying this function will iterate through all possible
|
|
Packit |
67cb25 |
permutations of a given order.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_prev (gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function steps backwards from the permutation :data:`p` to the
|
|
Packit |
67cb25 |
previous permutation in lexicographic order, returning
|
|
Packit |
67cb25 |
:macro:`GSL_SUCCESS`. If no previous permutation is available it returns
|
|
Packit |
67cb25 |
:macro:`GSL_FAILURE` and leaves :data:`p` unmodified.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Applying Permutations
|
|
Packit |
67cb25 |
=====================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permute (const size_t * p, double * data, size_t stride, size_t n)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function applies the permutation :data:`p` to the array :data:`data` of
|
|
Packit |
67cb25 |
size :data:`n` with stride :data:`stride`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permute_inverse (const size_t * p, double * data, size_t stride, size_t n)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function applies the inverse of the permutation :data:`p` to the
|
|
Packit |
67cb25 |
array :data:`data` of size :data:`n` with stride :data:`stride`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permute_vector (const gsl_permutation * p, gsl_vector * v)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function applies the permutation :data:`p` to the elements of the
|
|
Packit |
67cb25 |
vector :data:`v`, considered as a row-vector acted on by a permutation
|
|
Packit |
67cb25 |
matrix from the right, :math:`v' = v P`. The :math:`j`-th column of the
|
|
Packit |
67cb25 |
permutation matrix :math:`P` is given by the :math:`p_j`-th column of the
|
|
Packit |
67cb25 |
identity matrix. The permutation :data:`p` and the vector :data:`v` must
|
|
Packit |
67cb25 |
have the same length.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permute_vector_inverse (const gsl_permutation * p, gsl_vector * v)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function applies the inverse of the permutation :data:`p` to the
|
|
Packit |
67cb25 |
elements of the vector :data:`v`, considered as a row-vector acted on by
|
|
Packit |
67cb25 |
an inverse permutation matrix from the right, :math:`v' = v P^T`. Note
|
|
Packit |
67cb25 |
that for permutation matrices the inverse is the same as the transpose.
|
|
Packit |
67cb25 |
The :math:`j`-th column of the permutation matrix :math:`P` is given by
|
|
Packit |
67cb25 |
the :math:`:data:`p`_j`-th column of the identity matrix. The permutation :data:`p`
|
|
Packit |
67cb25 |
and the vector :data:`v` must have the same length.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permute_matrix (const gsl_permutation * p, gsl_matrix * A)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function applies the permutation :data:`p` to the matrix :data:`A` from
|
|
Packit |
67cb25 |
the right, :math:`A' = A P`. The :math:`j`-th column of the
|
|
Packit |
67cb25 |
permutation matrix :math:`P` is given by the :math:`p_j`-th column of the
|
|
Packit |
67cb25 |
identity matrix. This effectively permutes the columns of :data:`A` according
|
|
Packit |
67cb25 |
to the permutation :data:`p`, and so the number of columns of :data:`A` must
|
|
Packit |
67cb25 |
equal the size of the permutation :data:`p`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_mul (gsl_permutation * p, const gsl_permutation * pa, const gsl_permutation * pb)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function combines the two permutations :data:`pa` and :data:`pb` into a
|
|
Packit |
67cb25 |
single permutation :data:`p`, where :math:`p = pa * pb`
|
|
Packit |
67cb25 |
The permutation :data:`p` is equivalent to applying :data:`pb` first and
|
|
Packit |
67cb25 |
then :data:`pa`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Reading and writing permutations
|
|
Packit |
67cb25 |
================================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The library provides functions for reading and writing permutations to a
|
|
Packit |
67cb25 |
file as binary data or formatted text.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_fwrite (FILE * stream, const gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function writes the elements of the permutation :data:`p` to the
|
|
Packit |
67cb25 |
stream :data:`stream` in binary format. The function returns
|
|
Packit |
67cb25 |
:macro:`GSL_EFAILED` if there was a problem writing to the file. Since the
|
|
Packit |
67cb25 |
data is written in the native binary format it may not be portable
|
|
Packit |
67cb25 |
between different architectures.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_fread (FILE * stream, gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function reads into the permutation :data:`p` from the open stream
|
|
Packit |
67cb25 |
:data:`stream` in binary format. The permutation :data:`p` must be
|
|
Packit |
67cb25 |
preallocated with the correct length since the function uses the size of
|
|
Packit |
67cb25 |
:data:`p` to determine how many bytes to read. The function returns
|
|
Packit |
67cb25 |
:macro:`GSL_EFAILED` if there was a problem reading from the file. The
|
|
Packit |
67cb25 |
data is assumed to have been written in the native binary format on the
|
|
Packit |
67cb25 |
same architecture.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_fprintf (FILE * stream, const gsl_permutation * p, const char * format)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function writes the elements of the permutation :data:`p`
|
|
Packit |
67cb25 |
line-by-line to the stream :data:`stream` using the format specifier
|
|
Packit |
67cb25 |
:data:`format`, which should be suitable for a type of :data:`size_t`.
|
|
Packit |
67cb25 |
In ISO C99 the type modifier :code:`z` represents :code:`size_t`, so
|
|
Packit |
67cb25 |
:code:`"%zu\n"` is a suitable format [#f1]_.
|
|
Packit |
67cb25 |
The function returns :macro:`GSL_EFAILED` if there was a problem writing
|
|
Packit |
67cb25 |
to the file.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_fscanf (FILE * stream, gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function reads formatted data from the stream :data:`stream` into the
|
|
Packit |
67cb25 |
permutation :data:`p`. The permutation :data:`p` must be preallocated with
|
|
Packit |
67cb25 |
the correct length since the function uses the size of :data:`p` to
|
|
Packit |
67cb25 |
determine how many numbers to read. The function returns
|
|
Packit |
67cb25 |
:macro:`GSL_EFAILED` if there was a problem reading from the file.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Permutations in cyclic form
|
|
Packit |
67cb25 |
===========================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
A permutation can be represented in both *linear* and *cyclic*
|
|
Packit |
67cb25 |
notations. The functions described in this section convert between the
|
|
Packit |
67cb25 |
two forms. The linear notation is an index mapping, and has already
|
|
Packit |
67cb25 |
been described above. The cyclic notation expresses a permutation as a
|
|
Packit |
67cb25 |
series of circular rearrangements of groups of elements, or
|
|
Packit |
67cb25 |
*cycles*.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
For example, under the cycle (1 2 3), 1 is replaced by 2, 2 is replaced
|
|
Packit |
67cb25 |
by 3 and 3 is replaced by 1 in a circular fashion. Cycles of different
|
|
Packit |
67cb25 |
sets of elements can be combined independently, for example (1 2 3) (4
|
|
Packit |
67cb25 |
5) combines the cycle (1 2 3) with the cycle (4 5), which is an exchange
|
|
Packit |
67cb25 |
of elements 4 and 5. A cycle of length one represents an element which
|
|
Packit |
67cb25 |
is unchanged by the permutation and is referred to as a *singleton*.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
It can be shown that every permutation can be decomposed into
|
|
Packit |
67cb25 |
combinations of cycles. The decomposition is not unique, but can always
|
|
Packit |
67cb25 |
be rearranged into a standard *canonical form* by a reordering of
|
|
Packit |
67cb25 |
elements. The library uses the canonical form defined in Knuth's
|
|
Packit |
67cb25 |
*Art of Computer Programming* (Vol 1, 3rd Ed, 1997) Section 1.3.3,
|
|
Packit |
67cb25 |
p.178.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The procedure for obtaining the canonical form given by Knuth is,
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
#. Write all singleton cycles explicitly
|
|
Packit |
67cb25 |
#. Within each cycle, put the smallest number first
|
|
Packit |
67cb25 |
#. Order the cycles in decreasing order of the first number in the cycle.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
For example, the linear representation (2 4 3 0 1) is represented as (1
|
|
Packit |
67cb25 |
4) (0 2 3) in canonical form. The permutation corresponds to an
|
|
Packit |
67cb25 |
exchange of elements 1 and 4, and rotation of elements 0, 2 and 3.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The important property of the canonical form is that it can be
|
|
Packit |
67cb25 |
reconstructed from the contents of each cycle without the brackets. In
|
|
Packit |
67cb25 |
addition, by removing the brackets it can be considered as a linear
|
|
Packit |
67cb25 |
representation of a different permutation. In the example given above
|
|
Packit |
67cb25 |
the permutation (2 4 3 0 1) would become (1 4 0 2 3). This mapping has
|
|
Packit |
67cb25 |
many applications in the theory of permutations.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_linear_to_canonical (gsl_permutation * q, const gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function computes the canonical form of the permutation :data:`p` and
|
|
Packit |
67cb25 |
stores it in the output argument :data:`q`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: int gsl_permutation_canonical_to_linear (gsl_permutation * p, const gsl_permutation * q)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function converts a permutation :data:`q` in canonical form back into
|
|
Packit |
67cb25 |
linear form storing it in the output argument :data:`p`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: size_t gsl_permutation_inversions (const gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function counts the number of inversions in the permutation
|
|
Packit |
67cb25 |
:data:`p`. An inversion is any pair of elements that are not in order.
|
|
Packit |
67cb25 |
For example, the permutation 2031 has three inversions, corresponding to
|
|
Packit |
67cb25 |
the pairs (2,0) (2,1) and (3,1). The identity permutation has no
|
|
Packit |
67cb25 |
inversions.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: size_t gsl_permutation_linear_cycles (const gsl_permutation * p)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function counts the number of cycles in the permutation :data:`p`, given in linear form.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. function:: size_t gsl_permutation_canonical_cycles (const gsl_permutation * q)
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
This function counts the number of cycles in the permutation :data:`q`, given in canonical form.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Examples
|
|
Packit |
67cb25 |
========
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The example program below creates a random permutation (by shuffling the
|
|
Packit |
67cb25 |
elements of the identity) and finds its inverse.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. include:: examples/permshuffle.c
|
|
Packit |
67cb25 |
:code:
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Here is the output from the program::
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
$ ./a.out
|
|
Packit |
67cb25 |
initial permutation: 0 1 2 3 4 5 6 7 8 9
|
|
Packit |
67cb25 |
random permutation: 1 3 5 2 7 6 0 4 9 8
|
|
Packit |
67cb25 |
inverse permutation: 6 0 3 1 7 2 5 4 9 8
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The random permutation :code:`p[i]` and its inverse :code:`q[i]` are
|
|
Packit |
67cb25 |
related through the identity :code:`p[q[i]] = i`, which can be verified
|
|
Packit |
67cb25 |
from the output.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The next example program steps forwards through all possible third order
|
|
Packit |
67cb25 |
permutations, starting from the identity,
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. include:: examples/permseq.c
|
|
Packit |
67cb25 |
:code:
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
Here is the output from the program::
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
$ ./a.out
|
|
Packit |
67cb25 |
0 1 2
|
|
Packit |
67cb25 |
0 2 1
|
|
Packit |
67cb25 |
1 0 2
|
|
Packit |
67cb25 |
1 2 0
|
|
Packit |
67cb25 |
2 0 1
|
|
Packit |
67cb25 |
2 1 0
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The permutations are generated in lexicographic order. To reverse the
|
|
Packit |
67cb25 |
sequence, begin with the final permutation (which is the reverse of the
|
|
Packit |
67cb25 |
identity) and replace :func:`gsl_permutation_next` with
|
|
Packit |
67cb25 |
:func:`gsl_permutation_prev`.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
References and Further Reading
|
|
Packit |
67cb25 |
==============================
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
The subject of permutations is covered extensively in the following,
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
* Donald E. Knuth, The Art of Computer Programming: Sorting and
|
|
Packit |
67cb25 |
Searching (Vol 3, 3rd Ed, 1997), Addison-Wesley, ISBN 0201896850.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
For the definition of the *canonical form* see,
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
* Donald E. Knuth, The Art of Computer Programming: Fundamental
|
|
Packit |
67cb25 |
Algorithms (Vol 1, 3rd Ed, 1997), Addison-Wesley, ISBN 0201896850.
|
|
Packit |
67cb25 |
Section 1.3.3, An Unusual Correspondence, p.178--179.
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. rubric:: Footnotes
|
|
Packit |
67cb25 |
|
|
Packit |
67cb25 |
.. [#f1] In versions of the GNU C library prior to the ISO C99 standard,
|
|
Packit |
67cb25 |
the type modifier :code:`Z` was used instead.
|