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

[hv at crypt.org]

Earlier I wrote:
:franktaw at netscape.net wrote:
::Next question: for n = 4..9, a(n) = n(n+1)/2 - 2. Is there a general 
::solution of this length? (If so, does it continue to be optimal?)

I think this should read: a(n) = n(n-1)/2 - 2.

:I had hoped given some "fairly good" solution it might be obvious how
:to adapt it to approach optimality, but I don't see it - adapting q(n)
:to shuffle 2 symbols at a time, for example, gives l^n (xlxrr)^n x, which
:might improve the subordinate terms but cannot improve the dominant 3/4 n^2.

Ah, we need to zigzag.

Let Z_2 = x, Z_3 = xlxrx, and Z_{n+2} = (xl)^n (xr)^n xl Z_n for n+2>3.
Then Z_n is equivalent to: reverse first n symbols, and rotate left
floor(n/2)-1 times. Z_n requires n^2-n-1 operations. Additionally let
Z'_n be the same as Z_n but with each left/right shift reversed, which
is equivalent to: rotate right ceil(n/2)+1 times, reverse first n
symbols, rotate left floor(n/2)-1 times.

Then if I've calculated correctly this gives solutions requiring n(n-1)/2-2
operations for all n>=4:
  Z_{2m  } l^{m+1}  Z_{2m  } r^{m-1}     n=4m,
  Z_{2m+1} r^{m+1} Z'_{2m  } r^{m-1}     n=4m+1
  Z_{2m+1} l^{m+2}  Z_{2m+1} r^{m-1}     n=4m+2,
  Z_{2m+2} l^{m+2}  Z_{2m+1} r^{m-1}     n=4m+3

The resulting operation sequences look like this:
 4:  4 x ll x
 5:  8 xlxrx rr x
 6: 13 xlxrx lll xlxrx
 7: 19 xlxlxrxrxlx lll xlxrx
 8: 26 xlxlxrxrxlx lll xlxlxrxrxlx r
 9: 34 xlxlxlxrxrxrxlxlxrx rrr xrxrxlxlxrx r
10: 43 xlxlxlxrxrxrxlxlxrx llll xlxlxlxrxrxrxlxlxrx r
11: 53 xlxlxlxlxrxrxrxrxlxlxlxrxrxlx llll xlxlxlxrxrxrxlxlxrx r
12: 64 xlxlxlxlxrxrxrxrxlxlxlxrxrxlx llll xlxlxlxlxrxrxrxrxlxlxlxrxrxlx rr

So I think a(n) <= n(n-1)/2 - 2 for n >= 4.

It may also be of interest to note the number of minimal-length solutions
of a(n) for n in 1..10 goes like: 1, 3, 2, 2, 2, 6, 6, 32, 32, 240.

Maybe it is also possible to establish a lower bound of n(n-2)/2-2
by showing that we require the (n^2)/4 swaps used in these solutions.

Hugo