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

Christopher Gribble chris.eveswell at virgin.net
Tue Jun 15 14:35:16 CEST 2010


Here are the operation sequences in lexicographic order for all shortest
paths for 2 <= n <= 7:

n    len	num     sequence
2	 1	  3	  l
			  r
			  x

3	 2	  2	  lx
			  xr

4	 4	  2	  xllx
			  xrrx

5	 8	  2	  xllxlxrx
			  xlxrxrrx

6	13	  6	  lxlxrxrrxrxlx
			  lxrxlxllxlxrx
			  xlxrxlllxlxrx
			  xlxrxrrrxlxrx
			  xlxrxrrxrxlxr
			  xrxlxllxlxrxr

7	19	  6	  lxlxrxrrxrxrxlxlxrx
			  lxlxrxrxlxlxllxlxrx
			  xlxlxrxrxlxlllxlxrx
			  xlxrxrrrxrxlxlxrxrx
			  xlxrxrrxrxrxlxlxrxr
			  xlxrxrxlxlxllxlxrxr

I would calculate operation sequences for n > 7 but my PC still runs out of
memory.
Python 2.6.5 seems to have some problem in making use of the page file.  The
program
becomes unresponsive with no wait chain.

Best regards,

Chris Gribble

-----Original Message-----
From: seqfan-bounces at list.seqfan.eu [mailto:seqfan-bounces at list.seqfan.eu]
On Behalf Of hv at crypt.org
Sent: 08 June 2010 3:21 PM
To: hv at crypt.org
Cc: Sequence Fanatics Discussion list
Subject: [seqfan] Re: A048200 variant: invert [1, 2, ..., n] allowing one
swap and two shift-rotate operations

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


_______________________________________________

Seqfan Mailing list - http://list.seqfan.eu/






More information about the SeqFan mailing list