Left Inversion To Permutation - Maple Help

Iterator[Inversion]

 LeftInversionToPermutation
 convert left inversion table to permutation

 Calling Sequence LeftInversionToPermutation(b)

Parameters

 b - {list,rtable}; left inversion table

Description

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

Examples

 > $\mathrm{with}\left(\mathrm{Iterator}:-\mathrm{Inversion}\right):$
 > $b≔\left[0,2,1,0\right]$
 ${b}{≔}\left[{0}{,}{2}{,}{1}{,}{0}\right]$ (1)
 > $a≔\mathrm{LeftInversionToPermutation}\left(b\right)$
 ${a}{≔}\left[\begin{array}{cccc}{1}& {4}& {3}& {2}\end{array}\right]$ (2)
 > $\mathrm{PermutationToLeftInversion}\left(a\right)$
 $\left[\begin{array}{cccc}{0}& {2}& {1}& {0}\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, exercise 4, answers, pp. 591-592.  See also exercise 5; this can be made $\mathrm{O}\left(n\mathrm{log}\left(n\right)\right)$, rather than $\mathrm{O}\left({n}^{2}\right)$.

Compatibility

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