PermutationToLeftInversion 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 b 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, b, indexed from 1 to $n$, with $b_j$ the number of elements to the left of $j$ in a that are greater than $j$.

$\mathrm{with}\left(\mathrm{Iterator}:-\mathrm{Inversion}\right)\:$

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

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

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

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

$b≔\mathrm{Vector}\left(4\right)\:$

$\mathrm{PermutationToLeftInversion}\left(⟨4\,3\,2\,1⟩\,b\right)\:$

$b$

$\left[\begin{array}{c}3\\ 2\\ 1\\ 0\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][PermutationToLeftInversion] command was introduced in Maple 2016.

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