[seqfan] A048200 variant: invert [1, 2, ..., n] allowing one swap and two shift-rotate operations

[Richard Mathar]

Here is another idea to ponder:
What is the minimum number of atomic operations [one of (i) rotate-left, (ii) rotate-right
(iii) or swap leftmost two elements ] to reverse a sequence of n distinct ordered elements?

This is simply a variant of A048200 which adds the rotation in the
other direction to the set of elementary operations. The outcome is
a(n)<= A048200(n), because this increase in flexibility usually achieves
reversion with a lower number of operations. I get (with x=swap pair
of left elements, l=rotate right, r = rotate left, notation defined as in A048200)

a(1) = 0 (sequence is already in order)
a(2) = 1 (any of the three operations turns AB into BA)
a(3) = 2 (take xl: ABC -> x -> BAC -> l -> CBA with two operations xl for example)
a(4) = 4 (take xrrx: ABCD -> x -> BACD -> r -> ACDB -> r -> CDBA -> x -> DCBA for example)
a(5) = 8 (take xrxlxllx: ABCDE -> x -> BACDE -> r -> ACDEB -> x -> CADEB -> l -> BCADE
            -> x -> CBADE -> l -> ECBAD -> l -> DECBA -> x -> EDCBA for example)
a(6) = 13 (take xrxlxllxlxrxl for example)
a(7) = 19, (take xrxlxlxrxrxrrxrxlxl for example)

Solutions can be encoded by vectors of 0, 1 and 2 in the ternary system (say, r=0, x=1 and l=2),
avoiding the "xx" and "lr" and "rl" combinations which are like "undo" operations and useless
if the number of steps is to be minimized.

RJM