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

[Christopher Gribble]

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.


#---------------------------------------------------------------------------
----
#
# Function:     Determines the minimum number of atomic operations to
reverse a
#               sequence of n distinct ordered elements e.g. [1,..,n], where
#               each atomic operation is one of:
#               (i)   rotate-left, denoted by l
#               (ii)  rotate-right, denoted by r
#               (iii) swap leftmost two elements, denoted by x
#               Disallow the following pairs of operations: "xx", "lr" and
"rl"
#               as their effect is neutral.
#
#               Each node in the directed acyclic graph constructed has one
#               predecessor and up to 3 successors.
#
# Last mod:     02/06/2010
#
#---------------------------------------------------------------------------
----
#
import networkx as nx
import string as sg

b = sg.letters      # The 52 uppercase and lowercase letters

for len_n in range(2, 10):
#
# Create an empty directed graph.  It will be a tree if it is kept acyclic.
#
  G = nx.DiGraph()
#
# Specify the root node as the initial sequence and add it to G.
#
  s = b[0:len_n]
  n = s
  G.add_node(n)
#
# Form the reverse of the root node as the desired outcome.
#
  r = ""
  for i in range(0, len_n):
    r = r + s[len_n - i - 1]
#
# Branch from each leaf in G until the reverse of the root node is
generated.
#
  reversed = "false"
#
# Create a temporary empty directed graph to hold a copy of G.
#
  H = nx.DiGraph()
  while (reversed == "false"):
    H = G.copy()
    for n in H:
      if H.degree(n) == 0:
#
#       This is the root node.
#
#       Apply "l".
#
        t = n[1:] + n[0]
        if t == r:
          reversed = "true"
        G.add_edge(n, t, op = "l")
#
#       Apply "r".
#
        t = n[len_n - 1] + n[:len_n - 1]
        if t == r:
          reversed = "true"
        G.add_edge(n, t, op = "r")
#
#       Apply "x".
#
        t = n[1] + n[0] + n[2:]
        if t == r:
          reversed = "true"
        G.add_edge(n, t, op = "x")

      elif len(H.successors(n)) == 0:
#
#       This is not the root node and is a leaf node.  It has only one
predecessor.
#
        u = H.predecessors(n)[0]
#
#       If operation to form leaf is not "r" then apply "l".
#
        if G.edge[u][n]["op"] != "r":
          t = n[1:] + n[0]
          if t in G:
            z = 0       # Dummy operation
          else:
            if t == r:
              reversed = "true"
            G.add_edge(n, t, op = "l")
#
#       If operation to form leaf is not "l" then apply "r".
#
        if G.edge[u][n]["op"] != "l":
          t = n[len_n - 1] + n[:len_n - 1]
          if t in G:
            z = 0       # Dummy operation
          else:
            if t == r:
              reversed = "true"
            G.add_edge(n, t, op = "r")
#
#       If operation to form leaf is not "x" then apply "x".
#
        if G.edge[u][n]["op"] != "x":
          t = n[1] + n[0] + n[2:]
          if t in G:
            z = 0       # Dummy operation
          else:
            if t == r:
              reversed = "true"
            G.add_edge(n, t, op = "x")
#
# Determine shortest path to reverse of root node and its length.
#
  sp = nx.shortest_path(G, source=s, target=r, weighted=False)
  spl = nx.shortest_path_length(G, source=s, target=r, weighted=False)
#
# Extract operations used to construct shortest path from the attribute
dictionary for each edge in the path.
#
  op_str = ""
  for i in range(0, spl):
    attr_dict = G.get_edge_data(sp[i], sp[i+1], "op")
    op_str = op_str + attr_dict.get("op")
  a = str(spl) + " " + op_str
  print(a)

print("Output complete")


Best regards,

Chris Gribble


-----Original Message-----
From: seqfan-bounces at list.seqfan.eu [mailto:seqfan-bounces at list.seqfan.eu]
On Behalf Of Richard Mathar
Sent: 25 May 2010 6:00 PM
To: seqfan at seqfan.eu
Subject: [seqfan] A048200 variant: invert [1, 2, ..., n] allowing one swap
and two shift-rotate operations


Here is another idea to ponder:
What is the minimum number of atomic operations [one of (i) rotate-left,
(ii) rotate-right
(iii) or swap leftmost two elements ] to reverse a sequence of n distinct
ordered elements?

This is simply a variant of A048200 which adds the rotation in the
other direction to the set of elementary operations. The outcome is
a(n)<= A048200(n), because this increase in flexibility usually achieves
reversion with a lower number of operations. I get (with x=swap pair
of left elements, l=rotate right, r = rotate left, notation defined as in
A048200)

a(1) = 0 (sequence is already in order)
a(2) = 1 (any of the three operations turns AB into BA)
a(3) = 2 (take xl: ABC -> x -> BAC -> l -> CBA with two operations xl for
example)
a(4) = 4 (take xrrx: ABCD -> x -> BACD -> r -> ACDB -> r -> CDBA -> x ->
DCBA for example)
a(5) = 8 (take xrxlxllx: ABCDE -> x -> BACDE -> r -> ACDEB -> x -> CADEB ->
l -> BCADE
            -> x -> CBADE -> l -> ECBAD -> l -> DECBA -> x -> EDCBA for
example)
a(6) = 13 (take xrxlxllxlxrxl for example)
a(7) = 19, (take xrxlxlxrxrxrrxrxlxl for example)

Solutions can be encoded by vectors of 0, 1 and 2 in the ternary system
(say, r=0, x=1 and l=2),
avoiding the "xx" and "lr" and "rl" combinations which are like "undo"
operations and useless
if the number of steps is to be minimized.

RJM


_______________________________________________

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