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

[Christopher Gribble]

Hugo,

Thanks for this.  There had to be a better way!

Chris

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

"Christopher Gribble" <chris.eveswell at virgin.net> wrote:
:Hi Richard,
:
:I get the following with the Python program listed below:
:
:n a(n)  Operation Sequence
:2    1  x
:3    2  lx
:4    4  xrrx
:5    8  xllxlxrx
:6   13  xrxlxllxlxrxr
:7   19  lxlxrxrrxrxrxlxlxrx
:8   26  xlxlxrxrxlxrrrxrxrxlxlxrxr
:9   34  xlxlxrxrxlxlllxlxlxlxrxrxrxlxlxrxr
:
:I could not calculate a(10) as my PC ran out of its 12GB of memory.
:Perhaps there is a more efficient approach.

I find a(10)=43.

Below is a perl program that aims to minimize memory usage by storing
just a count for each of the n! arrangements. On my system it used 6.8MB
to calculate a(10) in just under 10m. An equivalent written in C should
I think be able to find at least up to a(13) with reasonable time and space
requirements (a few hours and 6.2GB) - beware though that 13! > 2^32.

With a suitable encoding to distinguish the forward and reverse paths,
you could search from both ends simultaneously to roughly double the speed
without increasing the memory requirements.

Note that this code does not record the actual path, so I can't report
that. However its agreement with your results for a(1)..a(9) gives me
some confidence in its correctness. It could be modified to use an extra
2 bits to record the operation used so that the actual path could easily
be reconstructed.

Hugo