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

[franktaw at netscape.net]

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.

Franklin T. Adams-Watters

-----Original Message-----
From: hv at crypt.org

"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
---
#!/usr/bin/perl -w
use strict;

=head The problem

Determine the minimum number of operations to reverse the sequence 
[1..n],
where the available operations are:
   'l': rotate left; 'r': rotate right; 'x': swap leftmost pair of 
elements

I represent a sequence as an index by packing such that index[n..1]=0 
and
index[1..n]=n!-1. The state of knowledge is stored in a vector of k-bit
integers reporting the length of the shortest path to this sequence from
the starting point.

To minimize memory usage, I do not record the list of sequences that are
to be processed, but (at stage m) search the list for length-(m-1) paths
previously recorded.

=cut

my $n = shift(@ARGV) || 1;
my $k = shift(@ARGV) || 8;
my $result = find_best();
print "a($n) = $result\n";
exit 0;

sub find_best {
    my $v = "";
     # This is actually depth 0, but we store as 1 to distinguish 
sequences
    # not yet reached.
    my $depth = 1;
     # Seed the vector with our starting point. (Usefully this also 
pre-extends
    # the vector, so perl won't ever need to resize it.)
    vec($v, factorial($n) - 1, $k) = $depth;
    while (vec($v, 0, $k) == 0) {
        for my $index (0 .. factorial($n) - 1) {
            next unless vec($v, $index, $k) == $depth;
            for my $next (reachable($index)) {
                next if vec($v, $next, $k);
                vec($v, $next, $k) = $depth + 1;
            }
        }
        ++$depth;
    }
    return $depth - 1;
}

sub reachable {
    my $index = shift;
    my $seq = index_to_seq($index);
     # under our representation, operation 'x' on a sequence is 
equivalent to
    # 'xor 1' on an index.
    return (
        ($index ^ 1),
        seq_to_index([ @$seq[1..$n-1], $$seq[0] ]),
        seq_to_index([ $$seq[$n-1], @$seq[0..$n-2] ]),
    );
}

sub index_to_seq {
    my $index = $_[0];
    my @a;
    for (1 .. $n) {
        my $q = $index % $_;
        $index = int($index / $_);
        # increment existing elements >= the new element
        $_ < $q || ++$_ for @a;
        push @a, $q;
    }
    return \@a;
}

sub seq_to_index {
    my @a = @{ $_[0] };
    my $index = 0;
    while (@a) {
        my $q = pop @a;
        # decrement existing elements > the new element
        $_ < $q || --$_ for @a;
        $index += $q * factorial(scalar @a);
    }
    return $index;
}

{
    my @f;
    sub factorial {
        $f[$_[0]] ||= $_[0] < 2 ? 1 : $_[0] * factorial($_[0] - 1);
    }
}



_______________________________________________

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