UNICYCLE
Permutations with a Single Cycle

UNICYCLE is a MATLAB 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 MATLAB library which includes many combinatorial routines.

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

Source Code:

• i4_factorial.m, computes the factorial of N.
• i4_modp.m, returns the nonnegative remainder of I4 division.
• i4_uniform.m, returns a scaled pseudorandom I4.
• i4_wrap.m, forces an I4 to lie between given limits by wrapping.
• i4vec_indicator.m, sets an I4VEC to the indicator vector.
• i4vec_reverse.m, reverses the elements of an I4VEC.
• perm_check.m, checks a representation of a permutation.
• perm_enum.m, enumerates the permutations on N digits.
• perm_inverse.m, computes the inverse of a permutation.
• perm_is_unicycle.m, is TRUE if a permutation is a unicycle.
• perm_lex_next.m, computes the lexicographic permutation successor.
• perm_lex_rank.m, computes the lexicographic rank of a permutation.
• perm_lex_unrank.m, computes the permutation of given lexicographic rank.
• perm_print.m, prints a permutation.
• perm_random.m, selects a random permutation of N objects.
• timestamp.m, prints the current YMDHMS date as a time stamp.
• unicycle_check.m, checks that a vector represents a unicycle.
• unicycle_enum.m, enumerates the unicycles.
• unicycle_index.m, returns the index form of a unicycle.
• unicycle_index_print.m, prints a unicycle given in index form.
• unicycle_index_to_sequence.m, converts a unicycle from index o sequence form.
• unicycle_inverse.m, returns the inverse of a unicycle.
• unicycle_next.m, generates unicycles in lexical order, one at a time.
• unicycle_print.m, prints a unicycle given in sequence form.
• unicycle_random.m, selects a random unicycle of N objects.
• unicycle_rank.m, computes the rank of a unicycle.
• unicycle_unrank.m, "unranks" a unicycle.

Examples and Tests:

• unicycle_test.m, a sample calling program.
• unicycle_test_output.txt, the output file.
• unicycle_test01.m, tests PERM_IS_UNICYCLE.
• unicycle_test02.m, tests UNICYCLE_ENUM.
• unicycle_test03.m, tests UNICYCLE_INVERSE;
• unicycle_test04.m, tests UNICYCLE_NEXT.
• unicycle_test05.m, tests UNICYCLE_RANDOM;
• unicycle_test06.m, tests UNICYCLE_RANK.
• unicycle_test07.m, tests UNICYCLE_UNRANK.
• unicycle_test08.m, tests UNICYCLE_INDEX, UNICYCLE_INDEX_TO_SEQUENCE.

You can go up one level to the MATLAB source codes.