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

[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);
    }
}