Permutations¶
This chapter describes functions for creating and manipulating permutations. A permutation is represented by an array of integers in the range 0 to , where each value occurs once and only once. The application of a permutation to a vector yields a new vector where . For example, the array represents a permutation which exchanges the last two elements of a four element vector. The corresponding identity permutation is .
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 rowvectors in the form rather than columnvectors, when permuting the elements of a vector.
The functions described in this chapter are defined in the header file
gsl_permutation.h
.
The Permutation struct¶

gsl_permutation
¶ 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
size_t
. Thegsl_permutation
structure looks like this:typedef struct { size_t size; size_t * data; } gsl_permutation;
Permutation allocation¶

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

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

void
gsl_permutation_init
(gsl_permutation * p)¶ This function initializes the permutation
p
to the identity, i.e. .

void
gsl_permutation_free
(gsl_permutation * p)¶ This function frees all the memory used by the permutation
p
.

int
gsl_permutation_memcpy
(gsl_permutation * dest, const gsl_permutation * src)¶ This function copies the elements of the permutation
src
into the permutationdest
. The two permutations must have the same size.
Accessing permutation elements¶
The following functions can be used to access and manipulate permutations.

size_t
gsl_permutation_get
(const gsl_permutation * p, const size_t i)¶ This function returns the value of the
i
th element of the permutationp
. Ifi
lies outside the allowed range of 0 to then the error handler is invoked and 0 is returned. An inline version of this function is used whenHAVE_INLINE
is defined.

int
gsl_permutation_swap
(gsl_permutation * p, const size_t i, const size_t j)¶ This function exchanges the
i
th andj
th elements of the permutationp
.
Permutation properties¶

size_t
gsl_permutation_size
(const gsl_permutation * p)¶ This function returns the size of the permutation
p
.

size_t *
gsl_permutation_data
(const gsl_permutation * p)¶ This function returns a pointer to the array of elements in the permutation
p
.

int
gsl_permutation_valid
(const gsl_permutation * p)¶ This function checks that the permutation
p
is valid. Then
elements should contain each of the numbers 0 ton  1
once and only once.
Permutation functions¶

void
gsl_permutation_reverse
(gsl_permutation * p)¶ This function reverses the elements of the permutation
p
.

int
gsl_permutation_inverse
(gsl_permutation * inv, const gsl_permutation * p)¶ This function computes the inverse of the permutation
p
, storing the result ininv
.

int
gsl_permutation_next
(gsl_permutation * p)¶ This function advances the permutation
p
to the next permutation in lexicographic order and returnsGSL_SUCCESS
. If no further permutations are available it returnsGSL_FAILURE
and leavesp
unmodified. Starting with the identity permutation and repeatedly applying this function will iterate through all possible permutations of a given order.

int
gsl_permutation_prev
(gsl_permutation * p)¶ This function steps backwards from the permutation
p
to the previous permutation in lexicographic order, returningGSL_SUCCESS
. If no previous permutation is available it returnsGSL_FAILURE
and leavesp
unmodified.
Applying Permutations¶
The following functions are defined in the header files gsl_permute.h
and gsl_permute_vector.h
.

int
gsl_permute
(const size_t * p, double * data, size_t stride, size_t n)¶ This function applies the permutation
p
to the arraydata
of sizen
with stridestride
.

int
gsl_permute_inverse
(const size_t * p, double * data, size_t stride, size_t n)¶ This function applies the inverse of the permutation
p
to the arraydata
of sizen
with stridestride
.

int
gsl_permute_vector
(const gsl_permutation * p, gsl_vector * v)¶ This function applies the permutation
p
to the elements of the vectorv
, considered as a rowvector acted on by a permutation matrix from the right, . The th column of the permutation matrix is given by the th column of the identity matrix. The permutationp
and the vectorv
must have the same length.

int
gsl_permute_vector_inverse
(const gsl_permutation * p, gsl_vector * v)¶ This function applies the inverse of the permutation
p
to the elements of the vectorv
, considered as a rowvector acted on by an inverse permutation matrix from the right, . Note that for permutation matrices the inverse is the same as the transpose. The th column of the permutation matrix is given by the th column of the identity matrix. The permutationp
and the vectorv
must have the same length.

int
gsl_permute_matrix
(const gsl_permutation * p, gsl_matrix * A)¶ This function applies the permutation
p
to the matrixA
from the right, . The th column of the permutation matrix is given by the th column of the identity matrix. This effectively permutes the columns ofA
according to the permutationp
, and so the number of columns ofA
must equal the size of the permutationp
.

int
gsl_permutation_mul
(gsl_permutation * p, const gsl_permutation * pa, const gsl_permutation * pb)¶ This function combines the two permutations
pa
andpb
into a single permutationp
, where The permutationp
is equivalent to applyingpb
first and thenpa
.
Reading and writing permutations¶
The library provides functions for reading and writing permutations to a file as binary data or formatted text.

int
gsl_permutation_fwrite
(FILE * stream, const gsl_permutation * p)¶ This function writes the elements of the permutation
p
to the streamstream
in binary format. The function returnsGSL_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.

int
gsl_permutation_fread
(FILE * stream, gsl_permutation * p)¶ This function reads into the permutation
p
from the open streamstream
in binary format. The permutationp
must be preallocated with the correct length since the function uses the size ofp
to determine how many bytes to read. The function returnsGSL_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.

int
gsl_permutation_fprintf
(FILE * stream, const gsl_permutation * p, const char * format)¶ This function writes the elements of the permutation
p
linebyline to the streamstream
using the format specifierformat
, which should be suitable for a type ofsize_t
. In ISO C99 the type modifierz
representssize_t
, so"%zu\n"
is a suitable format 1. The function returnsGSL_EFAILED
if there was a problem writing to the file.

int
gsl_permutation_fscanf
(FILE * stream, gsl_permutation * p)¶ This function reads formatted data from the stream
stream
into the permutationp
. The permutationp
must be preallocated with the correct length since the function uses the size ofp
to determine how many numbers to read. The function returnsGSL_EFAILED
if there was a problem reading from the file.
Permutations in cyclic form¶
A permutation can be represented in both linear and 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 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 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 canonical form by a reordering of elements. The library uses the canonical form defined in Knuth’s 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,
Write all singleton cycles explicitly
Within each cycle, put the smallest number first
Order the cycles in decreasing order of the first number in the cycle.
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.

int
gsl_permutation_linear_to_canonical
(gsl_permutation * q, const gsl_permutation * p)¶ This function computes the canonical form of the permutation
p
and stores it in the output argumentq
.

int
gsl_permutation_canonical_to_linear
(gsl_permutation * p, const gsl_permutation * q)¶ This function converts a permutation
q
in canonical form back into linear form storing it in the output argumentp
.

size_t
gsl_permutation_inversions
(const gsl_permutation * p)¶ This function counts the number of inversions in the permutation
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.

size_t
gsl_permutation_linear_cycles
(const gsl_permutation * p)¶ This function counts the number of cycles in the permutation
p
, given in linear form.

size_t
gsl_permutation_canonical_cycles
(const gsl_permutation * q)¶ This function counts the number of cycles in the permutation
q
, given in canonical form.
Examples¶
The example program below creates a random permutation (by shuffling the elements of the identity) 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;
const gsl_rng_type * T;
gsl_rng * r;
gsl_permutation * p = gsl_permutation_alloc (N);
gsl_permutation * q = gsl_permutation_alloc (N);
gsl_rng_env_setup();
T = gsl_rng_default;
r = gsl_rng_alloc (T);
printf ("initial permutation:");
gsl_permutation_init (p);
gsl_permutation_fprintf (stdout, p, " %u");
printf ("\n");
printf (" random permutation:");
gsl_ran_shuffle (r, p>data, N, sizeof(size_t));
gsl_permutation_fprintf (stdout, p, " %u");
printf ("\n");
printf ("inverse permutation:");
gsl_permutation_inverse (q, p);
gsl_permutation_fprintf (stdout, q, " %u");
printf ("\n");
gsl_permutation_free (p);
gsl_permutation_free (q);
gsl_rng_free (r);
return 0;
}
Here is the output from the program:
$ ./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 third 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);
gsl_permutation_free (p);
return 0;
}
Here is the output from the program:
$ ./a.out
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
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 gsl_permutation_next()
with
gsl_permutation_prev()
.
References and Further Reading¶
The subject of permutations is covered extensively in the following,
Donald E. Knuth, The Art of Computer Programming: Sorting and Searching (Vol 3, 3rd Ed, 1997), AddisonWesley, ISBN 0201896850.
For the definition of the canonical form see,
Donald E. Knuth, The Art of Computer Programming: Fundamental Algorithms (Vol 1, 3rd Ed, 1997), AddisonWesley, ISBN 0201896850. Section 1.3.3, An Unusual Correspondence, p.178–179.
Footnotes
 1
In versions of the GNU C library prior to the ISO C99 standard, the type modifier
Z
was used instead.