Permutation To Right Inversion - Maple Help

Iterator[Inversion]

 PermutationToRightInversion
 convert permutation to right inversion table

 Calling Sequence PermutationToRightInversion(a,c)

Parameters

 a - {list,rtable}; permutation of integers starting at one c - rtable; (optional) storage for inversion table

Description

 • PermutationToRightInversion returns the inversion table of a permutation, a, of the integers 1 to $n$.
 • The a parameter is a permutation of the consecutive integers from 1 to $n$; it may be a list or a one-dimensional rtable indexed from one.
 • The optional c parameter is a one-dimensional rtable indexed from 1 with at least $n$ slots. If provided, it is used to store the inversion table.
 • The output is an Array, c, indexed from 1 to $n$, with ${c}_{j}$ the number of elements to the right of $j$ in a that are less than $j$.

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}:-\mathrm{Inversion}\right):$
 > $\mathrm{PermutationToRightInversion}\left(\left[1,2,3,4\right]\right)$
 $\left[\begin{array}{cccc}{0}& {0}& {0}& {0}\end{array}\right]$ (1)
 > $\mathrm{PermutationToRightInversion}\left(\left[4,3,2,1\right]\right)$
 $\left[\begin{array}{cccc}{0}& {1}& {2}& {3}\end{array}\right]$ (2)

Use an existing vector to store the computed inversion table. Doing so reduces memory allocation when converting permutations to inversion tables in a loop.

 > $c≔\mathrm{Vector}\left(4\right):$
 > $\mathrm{PermutationToRightInversion}\left(⟨4,3,2,1⟩,c\right):$
 > $c$
 $\left[\begin{array}{c}{0}\\ {1}\\ {2}\\ {3}\end{array}\right]$ (3)

References

 Knuth, Donald Ervin. The Art of Computer Programming, volume 3, 2nd ed. sorting and searching, sec. 5.1.1, inversions, pp. 11-17 and exercise 7, p. 18.

Compatibility

 • The Iterator[Inversion][PermutationToRightInversion] command was introduced in Maple 2016.