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

[hv at crypt.org]

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?)

Here's a simple construction of *a* solution, though still a fair way
from optimal.

Let q(n) be the sequence: l^n (xr)^n x. Given |a|=1, |s|=n, q(n) changes
the permutation 'sat' to 'ast' in 3n+1 moves for all a, s, t.

Let r(n) = concat_1^{n-1}{ q(i) }. For a given permutation P with
|P| >= n, this reverses the first n symbols in sum_1^{n-1}{ 3n+1 }
= 1/2 (n-1)(3n-4) moves.

If |P| = 2n, we can reverse P with the sequence r(n) l^n r(n), which
requires 3n^2-6n+4 moves for n>=1.

If |P| = 2n+1, we can reverse P with the sequence r(n) l^n r(n+1), which
requires 3n^2-3n+2 moves for n>=1.

This gives as a lower bound a(n) <= floor((3n^2-12n+17)/4). Here's how that
compares to known values:

n: best this this-solution
 2:  1  1 l
 3:  2  2 lx
 4:  4  4 xllx
 5:  8  8 xllxlxrx
 6: 13 13 xlxrxlllxlxrx
 7: 19 20 xlxrxlllxlxrxllxrxrx
 8: 26 28 xlxrxllxrxrxllllxlxrxllxrxrx
 9: 34 38 xlxrxllxrxrxllllxlxrxllxrxrxlllxrxrxrx
10: 43 49 xlxrxllxrxrxlllxrxrxrxlllllxlxrxllxrxrxlllxrxrxrx
11: 53 62 xlxrxllxrxrxlllxrxrxrxlllllxlxrxllxrxrxlllxrxrxrxllllxrxrxrxrx

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.

Hugo