Introduction to composition and inversion of permutations.
Version of Wednesday 11 September 2024.

A characteristic operation performed on permutations is composition. It takes two permutations as inputs, and provides as output a new permutation whose components are those of the first input, rearranged according to the second. All three of the permutations will have the same number of elements.

Here is an example. The first input is σ = (6 3 8 2 9 7 4 5 0 1); the second input is τ = (1 5 6 0 4 3 8 2 9 7); and the output is π = (3 7 4 6 9 2 0 8 1 5). Using functional notation:

σ	index	0	1	2	3	4	5	6	7	8	9
	value	6	3	8	2	9	7	4	5	0	1
τ	index	0	1	2	3	4	5	6	7	8	9
	value	1	5	6	0	4	3	8	2	9	7
π = σ (τ)	index	0	1	2	3	4	5	6	7	8	9
	value	3	7	4	6	9	2	0	8	1	5

Here is the formula, using square brackets as the subscripting operator:

• π [0] = σ [τ [0]]
• π [1] = σ [τ [1]]
• π [2] = σ [τ [2]]
• and so forth

Warning: Some authors reverse the roles of σ and τ. This is critical, as σ (τ) ≠ τ (σ) in general.

Observe how the functional notation π = σ (τ) resembles the calculation formula π [n] = σ [τ [n]].

Although permzbis use numbers, the mechanism of composition might become clearer if letters are substituted for some of the numbers:

σ	index	0	1	2	3	4	5	6	7	8	9
	value	G	D	I	C	J	H	E	F	A	B
τ	index	0	1	2	3	4	5	6	7	8	9
	value	1	5	6	0	4	3	8	2	9	7
π = σ (τ)	index	0	1	2	3	4	5	6	7	8	9
	value	D	H	E	G	J	C	A	I	B	F

Throughout the literature can be found three equivalent notations for the same thing:

• π = σ (τ)
• π = σ ∘ τ
• π = στ

The permzbi program provides corresponding operators for two of them:

math	permzbi
σ (τ)	S (T)
σ ∘ τ	S | T
στ	none

C++ does not offer an operator that is invoked by typographical juxtaposition, although Stroustrup has offered (apperently in jest) a specification for a whitespace operator.

For any permutation, there is an identity permutation ι, of the same number of elements, such that ι ∘ σ = σ ∘ ι = σ. Any identity permutation is of the form (0, 1, 2, 3, …).

Every permutation has a unique inverse, often indicated by the superscript ⁻¹. The composition of a permutation and its inverse is the identity permutation.

As an example of the calculation, here is how to calculate the inverse of φ = (4 1 3 7 9 0 5 2 8 6):

Arrange permzbi φ thus:	φ	index	0	1	2	3	4	5	6	7	8	9
		value	4	1	3	7	9	0	5	2	8	6
Swap the indices and values:			4	1	3	7	9	0	5	2	8	6
			0	1	2	3	4	5	6	7	8	9
Sort by the new indices:	φ−1	index	0	1	2	3	4	5	6	7	8	9
		value	5	1	7	2	0	6	9	3	8	4

revealing that φ⁻¹ = (5 1 7 2 0 6 9 3 8 4).

The swap of the indices and values during the inversion process suggests a duality between the two, and the code presented here exploits that to a considerable extent. Two particular functions illustrate this:

    int permzbi::v_at_i (int const index) const; // "value at index"
    int permzbi::i_of_v (int const value) const; // "index of value"

The first is ordinary array indexing, while the second is a search operation. This means that v_at_i will typically run faster than i_of_v.

Adherents of strong and precise data typing might be inclined to use separate integer data types for the indices and values, but in some operations the values of one permzbi are used as indices to another permzbi, blurring any distinction.

The C++ Standard Library offers extensive support for iterators, as an alternative to indices, for selecting members of std::vectors. The parameter lists of the C++ functions appearing throughout the code, however, rarely call for iterators, preferring indices. That is because indices are numbers, and iterators are not. The inversion function demonstrates the close relationship between values and indices, and the values themselves are certainly numbers, not iterators. Of course, the inner workings of the functions as implemented here, which the user may ignore, use iterators when appropriate.

On top of that, indices make range checking a simple and direct process, but with iterators range checking is often difficult or complicated. Although it comes with a price of speed, range checking detects many errors and provides useful messages. In this program, it is turned on whenever permzbi_lib::permzbi_lib_safe equals true, and is then used extensively. Certain errors other than those of range violation will also be reported.