LeftInversionToPermutation constructs the permutation, $a$, of integers 1 to $n$ corresponding to the inversion table b, where $b_j$ is the number of elements to the left of $j$ in $a$ that are greater than $j$.

The b parameter is a left inversion table; it may be a list or one-dimensional rtable indexed from one, with $0\le b_j\le n-j$.

The output is an Array indexed from 1 to $n$ that contains a permutation of the integers from 1 to $n$.

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

$b≔\left[0\,2\,1\,0\right]$

$b≔\left[0\,2\,1\,0\right]$

$a≔\mathrm{LeftInversionToPermutation}\left(b\right)$

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

$\mathrm{PermutationToLeftInversion}\left(a\right)$

$\left[\begin{array}{cccc}0& 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, exercise 4, answers, pp. 591-592.  See also exercise 5; this can be made $\mathrm{O}\left(n\log \left(n\right)\right)$, rather than $\mathrm{O}\left(n^2\right)$.

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

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