[seqfan] Re: A048200 variant: invert [1, 2, ..., n] allowing one swap and two shift-rotate operations
franktaw at netscape.net
franktaw at netscape.net
Fri Jun 4 18:33:42 CEST 2010
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
More information about the SeqFan
mailing list