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:
| |||||||||||||||||||||||
Each cycles_@ class has a function to rebuild the permutation in a format that can be passed to a permu_@ constructor;
| |||||||||||||||||||||||
Each of the following converts a cycles_@ object of one type into an equivalent cycles_@ object of a different type.
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:
| |||||||||||||||||||||||
Each cycles_@ class has a function to display itself in human-readable form:
< 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:
| |||||||||||||||||||||||
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: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
permutation a: | 0 | 7 | 4 | 8 | 6 | 3 | 2 | 1 | 12 | 5 | 10 | 9 | 11 |
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 | |
indicator | cycle elements |
−1 | 0 |
−2 | 1, 7 |
−3 | 2, 4, 6 |
−6 | 3, 8, 12, 11, 9, 5 |
−1 | 10 |
The cycles are listed in the order that the programs's search happens to encounter them. As a result:
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 11which if needed can be passed to the permu_vec_0 constructor to construct a permutation.
Similar is the one-based equivalent:
position: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
permutation b: | 1 | 8 | 5 | 9 | 7 | 4 | 3 | 2 | 13 | 6 | 11 | 10 | 12 |
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 | |
indicator | cycle elements |
−1 | 1 |
−2 | 2, 8 |
−3 | 3, 5, 7 |
−6 | 4, 9, 13, 12, 10, 6 |
−1 | 11 |