UNICYCLE
Permutations with a Single Cycle

UNICYCLE is a C++ library which carries out some operations on permutations with a single cycle.

A permutation with a single cycle is a permutation P of N objects with the property that, for every object, it takes exactly N applications of P to restore an object to its original value.

Another way to think of this is that a permutation with a single cycle can be symbolized by a bracelet with N beads; the action of the permutation is to rotate the bracelet one position.

A permutation with a single cycle can be written in "sequence" form. Assuming the objects are labeled 1 through N, we start with 1, followed by P(1), followed by P(P(1)), and so on. Thus, the sequence (1,4,2,5,3) indicates the permutation which maps 1->4, 2->5, 3->1, 4->2, and 5->3.

A permutation with a single cycle is sometimes called a "cyclic permutation", but this term is also used with other meanings. Hence, we will affectionately call these objects "unicycles".

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

UNICYCLE is available in a C version and a C++ version and a FORTRAN77 version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

COMBO, a C++ library which includes many combinatorial routines.

SUBSET, a C++ library which generates, ranks and unranks various combinatorial objects.

Source Code:

• unicycle.cpp, the source code.
• unicycle.hpp, the source code.
• unicycle.sh, BASH commands to compile the source code.

Examples and Tests:

• unicycle_prb.cpp, a sample calling program.
• unicycle_prb.sh, BASH commands to compile and run the sample program.
• unicycle_prb_output.txt, the output file.

List of Routines:

• I4_FACTORIAL computes the factorial of N.
• I4_MAX returns the maximum of two I4's.
• I4_MIN returns the minimum of two I4's.
• I4_MODP returns the nonnegative remainder of I4 division.
• I4_UNIFORM returns a scaled pseudorandom I4.
• I4_WRAP forces an I4 to lie between given limits by wrapping.
• I4VEC_INDICATOR sets an I4VEC to the indicator vector.
• I4VEC_INDICATOR_NEW sets an I4VEC to the indicator vector.
• I4VEC_REVERSE reverses the elements of an I4VEC.
• PERM_CHECK checks a representation of a permutation.
• PERM_ENUM enumerates the permutations on N digits.
• PERM_INVERSE computes the inverse of a permutation.
• PERM_IS_UNICYCLE is TRUE if a permutation is a unicycle.
• PERM_LEX_NEXT computes the lexicographic permutation successor.
• PERM_LEX_RANK computes the lexicographic rank of a permutation.
• PERM_LEX_UNRANK computes the permutation of given lexicographic rank.
• PERM_PRINT prints a permutation.
• PERM_RANDOM selects a random permutation of N objects.
• S_LEN_TRIM returns the length of a string to the last nonblank.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• UNICYCLE_CHECK checks that a vector represents a unicycle.
• UNICYCLE_ENUM enumerates the unicycles.
• UNICYCLE_INDEX returns the index form of a unicycle.
• UNICYCLE_INDEX_PRINT prints a unicycle given in index form.
• UNICYCLE_INDEX_TO_SEQUENCE converts a unicycle from index to sequence form.
• UNICYCLE_INVERSE returns the inverse of a unicycle.
• UNICYCLE_NEXT generates unicycles in lexical order, one at a time.
• UNICYCLE_PRINT prints a unicycle given in sequence form.
• UNICYCLE_RANDOM selects a random unicycle of N objects.
• UNICYCLE_RANK computes the rank of a unicycle.
• UNICYCLE_UNRANK "unranks" a unicycle.

You can go up one level to the C++ source codes.