The at sign @ is used as a wildcard character in many names below.

The program contains four primary classes, named permu_@, all with the same general functionality. Supporting them are four secondary classes named cycles_@ respectively. In typical usage a programmer will select any one of the primary-secondary pairs, and can safely delete the code for the other three. Nonetheless, functions to convert from one pair to another are supplied if the programmer prefers to use multiple representations together. The classes are:

	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;

The first two pairs in the table use a std::array for storing permutation information while the last two use a std::vector. Although this internal container is not directly accessible to the user, it greatly influences the visible characteristics of its class.

Using the symbol sz to represent the size (i.e. the number of elements) of the permutation:

• The first and third pairs represent the permutation with integers 0 through sz − 1, as might be preferred by programmers who are experienced in the C family of programming languages. ("zero-based")
• The second and fourth pairs use integers 1 through sz, as is the custom among mathematicians. ("one-based")

Four preprocessor directives control which classes will be in use, as:

• #define USE_ARR_0 false // @_arr_0
• #define USE_ARR_1 true // @_arr_1
• #define USE_VEC_0 false // @_vec_0
• #define USE_VEC_1 false // @_vec_1

For most operations, the array will give faster performance than the vector, but the array requires that the size of the permutation be known at compile time. With the vector, specification of the size of the permutation can be delayed until run time. C++ novices will probably find the vector versions easier to use, due to the less frequent appearance of templates, whose syntax can be challenging.

In writing the code, the author emphasized clarity and simplicity so that a programmer who wants to edit the code has a better chance to understand it. No extraordinary attempts were made to increase efficiency, as different users have different needs in that regard. Along the same lines, no comprehensive effort was made to factor out the code common to all four classes, because (the author anticipates) most users will opt for only one of the classes.

The program is supplied in a large number of files, most of which are not mandatory:

files	comments
permu/A1_misc.h permu/A2_misc.h	always required
permu/B1_arr_0.h permu/B2_arr_0.h permu/B3_arr_0.h permu/B4_arr_0.h	required for @_arr_0
permu/C1_arr_1.h permu/C2_arr_1.h permu/C3_arr_1.h permu/C4_arr_1.h	required for @_arr_1
permu/D1_vec_0.h permu/D2_vec_0.h permu/D3_arr_0.h permu/D4_vec_0.h	required for @_vec_0
permu/E1_vec_1.h permu/E2_vec_1.h permu/E3_arr_0.h permu/E4_vec_1.h	required for @_vec_1
permu/F1_convert.h permu/F2_dist.h permu/F3_equal.h	possibly required, depending on the user's needs
demo/A_ctor.h demo/B_mult.h demo/C_invert.h demo/D_split.h demo/E_laminate.h demo/F_next_prev.h demo/G_reverse_pos.h demo/H_rotate_pos.h demo/I_trans_pos.h demo/J_shuffle.h demo/K_patterns.h demo/L_cycles.h demo/M_order.h demo/N_equal.h demo/O_reverse_val.h demo/P_rotate_val.h demo/Q_trans_val.h demo/R_distance.h demo_S_at_seek.h demo/T_convert.h	optional examples and tests
demo/X_general.h demo/Y_general.h demo/Z_general.h	optional, but dependent on the demo files above
main.cpp	to be customized by the user

Of great importance is this constant:

    constexpr bool permu_safe {true};

As long as permu_safe it is true, a great deal of run-time checking will be performed. If it is changed to false, most checking will be skipped, possibly yielding faster performance, but with an increase in the risk of undefined behavior — the error will often be one of these:

1. dereferencing an invalid iterator;
2. applying an out-of-range index to an std::array or std::vector;
3. constructing a permutation with repeated numbers, or with numbers that are out of range, or the wrong quantity of numbers; any of which will likely lead to problem 1 or 2.

Details of the permu_@ classes.

Covered on another page are the supporting cycles_@ classes, which are simpler, and which some users may not require at all.

Constructors. When permu_safe is true, each constructor verifies that any input provided is indeed a legal permutation.

explicit permu_arr_0 (bool const r = false); explicit permu_arr_1 (bool const r = false); explicit permu_vec_0 (int const sz, bool const r = false); explicit permu_vec_1 (int const sz, bool const r = false); The first two take the permutation size from the class's template parameter sz, and the last two from the function parameter sz. They produce the identity permutation if r is false, and a pseudorandom permutation (handy for testing) if r is true.

permu_arr_0 (std::initializer_list <int> i); permu_arr_1 (std::initializer_list <int> i); permu_vec_0 (std::initializer_list <int> i); permu_vec_1 (std::initializer_list <int> i); The first two ensure that the quantity of items in the initializer_list matches the template parameter sz. For the last two, the permutation size will be whatever the initializer_list provides.

template <typename input_iter> permu_arr_0 (input_iter begin, input_iter end); template <typename input_iter> permu_arr_1 (input_iter begin, input_iter end); template <typename input_iter> permu_vec_0 (input_iter begin, input_iter end); template <typename input_iter> permu_vec_1 (input_iter begin, input_iter end); The first two ensure that the quantity of items provided by the iterators matches the template parameter sz. For the last two, the permutation size will be whatever the iterators provide. While the constructor is being executed, end will not be deferenced, but begin will be dereferenced unless it equals end; this is in accord with C++ custom.

explicit permu_arr_0 (std::array<int,sz> const & g); explicit permu_arr_1 (std::array<int,sz> const & g); explicit permu_vec_0 (std::vector<int> const & g); explicit permu_vec_1 (std::vector<int> const & g); These load the permutation from a container filled elsewhere. In the first two, the size of the input container must match the template parameter sz. For the last two, the permutation size will equal the size of the input container. The type of the parameter (aside from const &) matches the type of the permutation's internal storage.

explicit permu_arr_0 (permu_arr_1<sz> const & o); explicit permu_arr_0 (permu_vec_0 const & o); explicit permu_arr_1 (permu_arr_0<sz> const & o); explicit permu_arr_1 (permu_vec_1 const & o); explicit permu_vec_0 (permu_vec_1 const & o); template <int sz> explicit permu_vec_0 (permu_arr_0<sz> const & o); explicit permu_vec_1 (permu_vec_0 const & o); template <int sz> explicit permu_vec_1 (permu_arr_1<sz> const & o); Each of these converts a permu_@ object of one type into the equivalent permu_@ of a different type. All incur the copying of data, and require that the source and destination be of the same size. Of the twelve conversion operations possible, the eight most likely to be needed are supplied: permu_arr_0 → increment each element permu_arr_1 ← decrement each element ↓ elements are unchanged ↑   ↓ elements are unchanged ↑ permu_vec_0 → increment each element permu_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 permu_@ object of one size to another size, because there is no clear criterion for what elements to insert or delete. Analogous functions are provided for the cycles_@ classes.

In all four permu_@ classes, the following are implemented as the compiler default: copy and move constructors; copy and move assignment operators; destructors.

"Almost" constructors.

static permu_arr_0 partial (std::initializer_list <int> i); template <typename forward_iter> static permu_arr_0 partial (forward_iter begin, forward_iter end); static permu_arr_1 partial (std::initializer_list <int> i); template <typename forward_iter> static permu_arr_1 partial (forward_iter begin, forward_iter end); static permu_vec_0 partial (int const sz, std::initializer_list <int> i); template <typename forward_iter> static permu_vec_0 partial (int const sz, forward_iter begin, forward_iter end); static permu_vec_1 partial (int const sz, std::initializer_list <int> i); template <typename forward_iter> static permu_vec_1 partial (int const sz, forward_iter begin, forward_iter end); These functions, each a member of the obvious class, produce a full permutation from a partial permutation. For example, either of these statements: permu_arr_0<13>::partial ({10, 8, 2, 5}); permu_vec_0::partial (13, {10, 8, 5, 2}); modifies the identity by rearranging those elements that are in the positions indicated by the arguments. Specifically, the function behaves as if those positions are first emptied, and then reloaded with the arguments, but now in the same order as in the argument list. Example: permu_arr_0 or permu_vec_0 identity 0 1 2 3 4 5 6 7 8 9 10 11 12 in progress 0 1   3 4   6 7   9   11 12 result 0 1 10 3 4 8 6 7 2 9 5 11 12 The one-based versions: permu_arr_1<13>::partial ({11, 9, 3, 6}); permu_vec_1::partial (13, {11, 9, 6, 3})) work similarly: permu_arr_1 or permu_vec_1 identity 1 2 3 4 5 6 7 8 9 10 11 12 13 in progress 1 2   4 5   7 8   10   12 13 result 1 2 11 4 5 9 7 8 3 10 6 12 13 Note that the template functions use forward iterators rather than input iterators, because they make two passes over the input. The partial functions are intended to help the user who wants to build a permutation by specifying its cycles. The method is to call partial to create a permu_@ object for each cycle, and then to combine them using operator* which is described below.

Basic calculations.

permu_arr_0 operator* (permu_arr_0 const & o) const; permu_arr_0 invert () const; and similarly for the other three classes operator* implements the permutation operation that is sometimes called multiplication, and sometimes called function composition. Authors differ on the sequence in which the inputs to this non-commutative operation are written, x * y versus y * x. Of course, the identity permutation commutes with anything. invert is defined so that x * x.invert() and x.invert() * x will both yield the identity permutation.

template <int tz> permu_arr_0<sz+tz> direct_sum (permu_arr_0<tz> const & x) const; template <int tz> permu_arr_0<sz+tz> skew_sum (permu_arr_0<tz> const & x) const; template <int tz> permu_arr_1<sz+tz> direct_sum (permu_arr_1<tz> const & x) const; template <int tz> permu_arr_1<sz+tz> skew_sum (permu_arr_1<tz> const & x) const; permu_vec_0 direct_sum (permu_vec_0 const & x) const; permu_vec_0 skew_sum (permu_vec_0 const & x) const; permu_vec_1 direct_sum (permu_vec_1 const & x) const; permu_vec_1 skew_sum (permu_vec_1 const & x) const; These calculate the direct or skew sum of two permutations. Despite the use of the word "sum", these operations are not commutative. The two permutations need not be the same size.

template <int tz> permu_arr_0<tz> front_split () const; template <int tz> permu_arr_0<tz> back_split () const; template <int tz> permu_arr_1<tz> front_split () const; template <int tz> permu_arr_1<tz> back_split () const; permu_vec_0 front_split (int const tz) const; permu_vec_0 back_split (int const tz) const; permu_vec_1 front_split (int const tz) const; permu_vec_1 back_split (int const tz) const; If a permutation could have been composed as a direct_sum or a skew_sum, these operations can return one or the other of the "addends": Each front_split operation attempts to return the first tz elements as a stand-alone permutation. Each back_split operation attempts to return the last tz elements as a stand-alone permutation. The trivial case, where tz equals zero or the size of the input permutation, is supported. If permu_safe is true, the program verifies that the split is indeed possible. Some permutations have many legal split points, while others have no split point that is nontrivial.

template <int tz> std::pair <permu_arr_0<tz>, permu_arr_0<sz−tz>> front_split_both () const; template <int tz> std::pair <permu_arr_0<sz−tz>, permu_arr_0<tz>> back_split_both () const; template <int tz> std::pair <permu_arr_1<tz>, permu_arr_1<sz−tz>> front_split_both () const; template <int tz> std::pair <permu_arr_1<sz−tz>, permu_arr_1<tz>> back_split_both () const; std::pair <permu_vec_0, permu_vec_0> front_split_both (int const tz) const; std::pair <permu_vec_0, permu_vec_0> back_split_both (int const tz) const; std::pair <permu_vec_1, permu_vec_1> front_split_both (int const tz) const; std::pair <permu_vec_1, permu_vec_1> back_split_both (int const tz) const; These operations return both parts of a split by way of a std::pair. They eliminate the redundant calculation of two invocations of front_split and/or back_split, but might be regarded as more complicated to use.

bool front_splittable (int const tz) const; bool back_splittable (int const tz) const; These indicate whether it would be legal to split a permutation at a certain point, but no split is performed.

bool separable () const; bool stack_sortable () const; These tell whether a permutation is separable or stack-sortable.

template <int tz> permu_arr_0<sz*tz> laminate (permu_arr_0<tz> const & x) const; template <int tz> permu_arr_1<sz*tz> laminate (permu_arr_1<tz> const & x) const; permu_vec_0 laminate (permu_vec_0 const & x) const; permu_vec_1 laminate (permu_vec_1 const & x) const; See detail here.

More operations.

The indexing of permutation elements depends on whether they are zero-based or one-based. The two example permutations below are equivalent in the sense that the conversion constructors above will convert either into the other. Note that if the permutation elements are zero-based, so are their position numbers; similarly for one-based.

permu_arr_0 or permu_vec_0
position	0	1	2	3	4	5	6	7	8
element	8	1	4	0	3	7	2	5	6
permu_arr_1 or permu_vec_1
position	1	2	3	4	5	6	7	8	9
element	9	2	5	1	4	8	3	6	7

One aspect of element numbering is C-style: when a range is given, the first position is inclusive, and the second position is exclusive. For example, if a function has formal parameters named lo and hi, and the function is called with actual parameters 2 and 6 respectively, the range effected will contain 2, 3, 4, and 5. This applies whether the permutation is zero-based or one-based.

For a zero-based permutation, the special value −1 indicates that a range is to extend through the last element; for a one-based permutation, the special value is 0. These values are analogous to the end() iterator frequently seen with the containers of the C++ Standard Library.

bool next_lexi (); bool prev_lexi (); bool next_SJT (); bool prev_SJT (); These replace a permutation with either the next or previous permutation, in either lexicographic or Steinhaus-Johnson-Trotter order. If either next function is called on the last permutation in the sequence, it is replaced with the first permutation, and false is returned. If either prev function is called on the first permutation in the sequence, it is replaced with the last permutation, and false is returned. Otherwise, true is returned. In both sequences, the identity permutation is regarded as the first. With lexicographical order, the last permutation is the reverse of the first. With SJT order, the last is the same as the first except that the first two elements (if there are that many) have been reversed. Example: zero-based one-based first (either) [ 0 1 2 3 4 5 6 ] [ 1 2 3 4 5 6 7 ] last (lexi) [ 6 5 4 3 2 1 0 ] [ 7 6 5 4 3 2 1 ] last (SJT) [ 1 0 2 3 4 5 6 ] [ 2 1 3 4 5 6 7 ] next_lexi and prev_lexi are merely wrappers for std::next_permutation and std::prev_permutation. On the other hand, the SJT functions are implemented in original code.

void reverse_position (int const lo = 0, int const hi = −1); // for permu_@_0 void reverse_position (int const lo = 1, int const hi = 0); // for permu_@_1 void reverse_value (int const lo = 0, int const hi = −1); // for permu_@_0 void reverse_value (int const lo = 1, int const hi = 0); // for permu_@_1 See detail here.

void rotate_position (int const lo, int const md, int const hi); void rotate_value (int const dist, int const lo = 0, int const hi = −1); // for permu_@_0 void rotate_value (int const dist, int const lo = 1, int const hi = 0); // for permu_@_1 See detail here.

void transpose_position (int const i, int const j, int const k = 1); void transpose_value (int const i, int const j, int const k = 1); See detail here.

void shuffle (bool const out_in, int const a, int const b); void unshuffle (bool const out_in, int const a, int const b); See detail here.

cycles_arr_0 get_cycles () const; // for permu_arr_0 cycles_arr_1 get_cycles () const; // for permu_arr_1 cycles_vec_0 get_cycles () const; // for permu_vec_0 cycles_vec_1 get_cycles () const; // for permu_vec_1 See detail here, including a discussion of the cycles_@ classes.

int inversion_count () const; int sign () const; inversion_count tells how many times an element in a lower-number position is greater than an element in a higher-number position. For the identity permutation, the answer is zero. Every permutation is even or odd: If inversion_count is an even number, sign will be +1, and the permutation is even. If inversion_count is an odd number, sign will be −1, and the permutation is odd.

int order () const; This returns a positive integer telling to what power (multiple invocations of operator*) the permutation must be raised in order to result in the identity permutation.

int at (int const i) const; int seek (int const n) const; The one-parameter at function returns a copy of the element whose location is the parameter. Prohibited is to modify exactly one element; this restriction is to prevent corruption of the permutation. seek does the opposite, returning the location of the element whose value is the parameter. std::array<int,sz> const & at () const; // for permu_arr_@ std::vector<int> const & at () const; // for permu_vec_@ The zero-parameter at functions return a constant reference to the container of the permutation's internal storage. Returned is a zero-based std::array or std::vector, even if it comes from a one-based permutation — this simply reflects how the Standard Library's containers are. In any case, the user can arbitrarily modify a copy of the returned container, and furnish it to a constructor to create a new permutation. Although the permu_@ classes are sequence containers internally, no iterators are provided. This is because, in order to prevent corruption of the permutation, any iterators could offer only the subset of operations that cannot modify the container, and these few are of limited usefulness. Of course, the user is always free to use the zero-parameter at in order to deliver a Standard Library container that has full iterator support.

constexpr int size () const; // for permu_arr_@ int size () const; // for permu_vec_@ The two size functions tell how many elements are in the permutation, which is precisely the size of the underlying std::array or std::vector. static constexpr int base {0}; // for permu_@_0 static constexpr int base {1}; // for permu_@_1 Although not functions, these public constants are listed here anyway.

template <typename permu> bool operator== (permu const & a, permu const & b); template <typename permu> bool operator!= (permu const & a, permu const & b); template <typename permu> bool operator>= (permu const & a, permu const & b); template <typename permu> bool operator<= (permu const & a, permu const & b); template <typename permu> bool operator> (permu const & a, permu const & b); template <typename permu> bool operator< (permu const & a, permu const & b); These nonmember functions compare permutations according to lexicographic order, and are merely wrappers for the corresponding operators of std::array or std::vector. In particular, operator< will provide the ordering required by an associative container such as std::map or std::set.

template <typename permu> int distance::cayley (permu const & a, permu const & b); template <typename permu> int distance::hamming (permu const & a, permu const & b); template <typename permu> double distance::minkowski (permu const & a, permu const & b, double const p); template <typename permu> int distance::maximum (permu const & a, permu const & b); template <typename permu> int distance::minimum (permu const & a, permu const & b); These nonmember functions calculate the distance between two permutations: cayley gives the minimum number of two-element swaps to convert one operand to the other. hamming counts the positions where the two permutations differ. minkowski calculates the pth root of the sum of the pth powers of the absolute values of the differences of corresponding elements. p must be positive. maximum (or Chebyshev) finds the two corresponding elements that have the greatest difference, as measured in absolute value, and returns that absolute value. minimum finds the two corresponding elements that have the smallest difference, as measured in absolute value, and returns that absolute value. Here is an example of the last two: permutation 3 2 8 0 7 1 4 6 5 permutation 1 0 7 6 2 4 5 3 8 differences 2 2 1 6 5 3 1 3 3 maximum = 6, minimum = 1

bool is_deranged () const; This member function tells whether the permutation is a derangement. template <typename permu> bool are_deranged (permu const & a, permu const & b) This nonmember function tells whether one permutation is a derangement of the other; they must be of the same size. This is true when the result of hamming equals their mutual size. In particular, it is also true when they are of size zero.

template <typename permu> double statistics::correlation (permu const & a, permu const & b); template <typename permu> double statistics::covariance (permu const & a, permu const & b); These nonmember functions calculate some standard bivariate statistics. Weighting is n rather than n−1 on the grounds that the entire population is available.

void view (std::ostream & o) const; This prints the permutation in human-readable form. The elements are listed between square brackets, with a two-character label at the end to indicate in what class the permutation is stored: permu_arr_0: [ 3 2 7 0 6 4 1 8 5 a0] permu_arr_1: [ 4 3 8 1 7 5 2 9 6 a1] permu_vec_0: [ 3 2 7 0 6 4 1 8 5 v0] permu_vec_1: [ 4 3 8 1 7 5 2 9 6 v1]

Demo classes. The user can call either of these functions:

• void demo_Y_general () // "Y"
• void demo_Z_general () // "Z"

Functions "Y" and "Z" rely on the settings in file demo/X_general.h to determine which routines to run.

"Y" and "Z" display the same information. If the user has activated at least two classes by way of the preprocessor directives (such as USE_ARR_0), "Y" and "Z" will present their respective results in different sequences, and the user can choose whichever is more convenient.