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

Richard Mathar mathar at strw.leidenuniv.nl
Tue May 25 18:59:34 CEST 2010

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.


More information about the SeqFan mailing list