[seqfan] Re: A048200 variant: invert [1, 2, ..., n] allowing one swap and two shift-rotate operations
Christopher Gribble
chris.eveswell at virgin.net
Wed Jun 2 14:04:57 CEST 2010
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/
More information about the SeqFan
mailing list