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

[franktaw at netscape.net]

I should have looked more closely at what you said you are doing. Now 
that I have, I don't think my approach can be made comparably fast.

Your approach could be done with just 2 bits per permutation, encoding 
"not yet reached", "reached this time", "reached last time", and 
"reached previously. This pretty well gives up getting the actual 
sequence of operations, however.

Keeping a count as you are doing, it isn't too hard to find the 
sequence of operations once you're done. Look at the 3 neighbors of the 
target to find one with a count one lower, then look at its two 
remaining neighbors, etc.

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

Franklin T. Adams-Watters

-----Original Message-----
From: 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