Next: , Previous: Reading and writing permutations, Up: Permutations

9.8 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,

  1. Write all singleton cycles explicitly
  2. Within each cycle, put the smallest number first
  3. 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.

— Function: 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 argument q.

— Function: 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 argument p.

— Function: 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.

— Function: 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.

— Function: 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.