[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:
:Another approach is to first find a reasonably good solution, then do a 
:depth-first search that fails when it reaches the length of the best 
:solution found so far. This will take a little longer, depending on how 
:good your first solution is (and how dense the optimal solutions are), 
:but it takes virtually no memory.
:
:In this case, it looks like a(n) <= a(n-1) + n, so you could just start 
:with that as a bound. If it that doesn't hold for some n, you'll fail 
:and have to retry with a bigger bound.

If I calculate correctly, assuming a(13) is around 76, this approach would
require about 2^76 steps compared to 76.13! ~= 2^39 steps, and with
a corresponding blowup for increasing n. I'm not sure that's practical
for calculating any values for which my approach runs out of memory.

Is there some way to prune this to better than 2^a(n) steps without
restoring the need for large gobs of memory? You can save a little
by spotting consecutive l^k or r^k where 2k>n, but it's not really
significant.

Maybe it is valuable to detect when you return to the starting sequence
and then record the pattern of moves as a cycle and check for any occurrence
of the recorded cycles (ignoring new cycles detected once you've used some
predefined limit of memory) - I think that could be done reasonably
efficiently (by building a DFA matcher), but the amount of pruning that
achieves is very dependent on how short the patterns are. (Note that,
in effect, we already do this in spotting the short patterns xx, lr and rl
to prune down from 3^a(n) steps.)

Hugo