Permutation To Left Inversion - Maple Help

Iterator[Inversion]

 PermutationToLeftInversion
 convert permutation to left inversion table

 Calling Sequence PermutationToLeftInversion(a,b)

Parameters

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

Description

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

Examples

 > $\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]$ (1)
 > $\mathrm{PermutationToLeftInversion}\left(\left[4,3,2,1\right]\right)$
 $\left[\begin{array}{cccc}{3}& {2}& {1}& {0}\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.

 > $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]$ (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][PermutationToLeftInversion] command was introduced in Maple 2016.