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$.

$\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]$

$\mathrm{PermutationToRightInversion}\left(\left[4\,3\,2\,1\right]\right)$

$\left[\begin{array}{cccc}0& 1& 2& 3\end{array}\right]$

$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]$

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.

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

For more information on Maple 2016 changes, see Updates in Maple 2016.