[seqfan] Re: A048200 variant: invert [1, 2, ..., n] allowing one swap and two shift-rotate operations
hv at crypt.org
hv at crypt.org
Tue Jun 8 16:21:19 CEST 2010
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
More information about the SeqFan
mailing list