| @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 |
| |