lehmer in A Sentence

1

The second step interprets this sequence as a Lehmer code or(almost equivalently) as an inversion table.

0

2

For the latter correspondence one could interpret the(reverse) sequence as a Lehmer code, and this gives a generation method first published in 1938 by Ronald Fisher and Frank Yates.

0

3

For this reason it does not seem useful, although certainly possible, to employ a special data structure that would allow performing the conversion from Lehmer code to permutation in O(n log n) time.

0

4

Moreover, the positions of the zeroes in the inversion table give the values of left-to-right maxima of the permutation( in the example 6, 8, 9) while the positions of the zeroes in the Lehmer code are the positions of the right-to-left minima( in the example positions the 4, 8, 9 of the values 1, 2, 5); this allows computing the distribution of such extrema among all permutations.

0