Home page.


There are four cycles_@ classes, corresponding to the four permu_@ classes, as shown in the following table which is repeated from the main page:

primary secondary
@_arr_0 template <int sz>
class permu_arr_0;
template <int sz>
class cycles_arr_0;
@_arr_1 template <int sz>
class permu_arr_1;
template <int sz>
class cycles_arr_1;
@_vec_0 class permu_vec_0; class cycles_vec_0;
@_vec_1 class permu_vec_1; class cycles_vec_1;

Each of the cycles_@ classes has only one ab ovo constructor, which is declared private, with the corresponding permu_@ class declared as a friend. Privacy is nececessary because a cycles_@ object depends on a permu_@ object to verify that the permutation under examination is valid.

For the user, each permu_@ class has a public member function to produce a cycles_@ object: from a permu_@ object that already exists:

  • cycles_arr_0<sz> permu_arr_0<sz>::get_cycles () const;
  • cycles_arr_1<sz> permu_arr_1<sz>::get_cycles () const;
  • cycles_vec_0 permu_vec_0::get_cycles () const;
  • cycles_vec_1 permu_vec_1::get_cycles () const;
Each cycles_@ class has a function to rebuild the permutation in a format that can be passed to a permu_@ constructor;
  • std::array<int,sz> rebuild () const; // for permu_arr_@
  • std::vector<int> rebuild () const; // for permu_vec_@
Each of the following converts a cycles_@ object of one type into an equivalent cycles_@ object of a different type.
  • explicit cycles_arr_0 (cycles_arr_1<sz> const & o);
  • explicit cycles_arr_0 (cycles_vec_0 const & o);
  • explicit cycles_arr_1 (cycles_arr_0<sz> const & o);
  • explicit cycles_arr_1 (cycles_vec_1 const & o);
  • explicit cycles_vec_0 (cycles_vec_1 const & o);
  • template <int sz>
    explicit cycles_vec_0 (cycles_arr_0<sz> const & o);
  • explicit cycles_vec_1 (cycles_vec_0 const & o);
  • template <int sz>
    explicit cycles_vec_1 (cycles_arr_1<sz> const & o);
All incur the copying of data, and require that the source and destination represent permutations of the same size. Of the twelve conversion operations possible, the eight most likely to be needed are supplied:

cycles_arr_0
increment each element
cycles_arr_1

decrement each element
elements
are unchanged
  elements
are unchanged
cycles_vec_0
increment each element
cycles_vec_1

decrement each element

If the "diagonal" conversions are needed, they can be achieved in a two-step operation.

No function is supplied to convert a cycles_@ object of one size to another size, because there is no clear criterion for what elements to insert or delete.

These are analogous to the conversions for permu_@ classes.

In all four cycles_@ classes, the following public functions are implemented as the compiler default:
  • copy and move constructors;
  • copy and move assignment operators;
  • destructors.
Each cycles_@ class has a function to display itself in human-readable form:
  • void view (std::ostream & o) const;
For example:
    < 13 0 cy -1  0 -2  1  7 -3  2  4  6 -6  3  8 12 11  9  5 -1 10  v0>
The first number is the size of the permutation, and the second number is the base: 0 or 1. Details are presented after the label "cy": the absolute value of each negative number is the length of a cycle, and the nonnegative numbers following it are the components of that cycle. The "v0" label denotes the class, with the same meaning as permu_@::view function.
This nonmember function:
  • template <typename cycles_a, typename cycles_b>
    bool are_conjugate (cycles_a const & a, cycles_b const & b);
returns true if a and b have the same pattern of cycles.

Each cycles_@ class has a zero-parameter function at which returns a constant reference to a container holding the cycle representation with negative and positive numbers similar to what the view function delivers.

With the cycles_vec_@ classes, the std::vector object returned by at will be precisely the size needed to contain the information. If the permutation contains sz elements, then the std::vector will contain anywhere from sz + 1 to sz × 2 components.

However, with the cycles_arr_@ classes there is an inconvenience. As a std::array must have its size established at compile time, the program must prepare for the worst case, returning a std::array that has sz × 2 components even if fewer are needed. The workaround employed here is to fill the unneeded locations with the int constant filler, which equals the most negative int, a number very unlikely to arise in normal calculations. In the case of a typical 32-bit two's complement signed integer, filler equals −2,147,483,648; but implementations can vary. The cycles_arr_@::view functions do not display the filler components.

The following examples rely on these equivalent permutations:

    permu_vec_0 const a {0, 7, 4, 8, 6, 3, 2, 1, 12, 5, 10,  9, 11};
    permu_vec_1 const b {1, 8, 5, 9, 7, 4, 3, 2, 13, 6, 11, 10, 12};

Here is permutation a shown with position numbers for convenience:

position: 0123456789101112
permutation a: 0748632112510911

Each get_cycles function produces an object of class cycles_@ that contains information about what cycles the permutation contains. In this example, the a.get_cycles() function returns a cycles_vec_0 object as follows:

    < 13 0 cy -1  0 -2  1  7 -3  2  4  6 -6  3  8 12 11  9  5 -1 10  v0>
Here is the breakdown:

permutation a
indicatorcycle elements
−10
−21, 7
−32, 4, 6
−63, 8, 12, 11, 9, 5
−110

The cycles are listed in the order that the programs's search happens to encounter them. As a result:

Some authors prefer other arrangements, such as:

If the cycles_vec_0 member function rebuild() is invoked, as a.get_cycles().rebuild(), returned is a std::vector<int> containing the elements of the permutation:

    0  7  4  8  6  3  2  1 12  5 10  9 11
which if needed can be passed to the permu_vec_0 constructor to construct a permutation.

Similar is the one-based equivalent:

position: 12345678910111213
permutation b: 18597432136111012

The cycles_vec_1 object returned by b.get_cycles() is:

    < 13 1 cy -1  1 -2  2  8 -3  3  5  7 -6  4  9 13 12 10  6 -1 11  v1>

Here is the breakdown:

permutation b
indicatorcycle elements
−11
−22, 8
−33, 5, 7
−64, 9, 13, 12, 10, 6
−111