# [r-t] Notating jump changes (was Blue line (/grid) generators / Jump Changes)

Alexander Holroyd holroyd at math.ubc.ca
Wed Jun 3 06:17:02 UTC 2015

```Actually I did find Don's post about the jump change algorithm rather
interesting.  (I've just been busy).

I don't know for sure whether Don's algorithm is correct (I expect it is).
However, after some thought I was able to find a nice simple algorithm of
my own, and I was able to prove that it works.  As an additional bonus, it
does away with the need for special treatment of cross changes and
external places.

It turns out to be a rather nice problem.  It seems confusing at first,
but with the right abstract picture it becomes simple.

As Don says, suppose we are given a "jump place notation" consisting of a
list of pairs (xy) indicating a jump from place x to place y (where
|x-y|>=2), and single numbers x meaning that xth place is made, with 1sts
and nths places perhaps omitted, and with the exception that the notation
cannot be an empty list except in the case of the cross change.  (So we
are not allowed to omit all external places in the pn 1 or n (odd stages)
or 1n (even stages)).  All other bells are to move by one position or make
an external place.

I will prove that any such notation corresponds to at most one change, and
furthermore that there is an easy algorithm that decides whether there is
a such a change, and if so returns it.

As in Don's approach, start by assigning bell x to place y for each (xy),
and bell x to place x for each explicitly given place x.  This leaves
perhaps some bells and some places unassigned, and these need to be
accommodated using steps of one place to the left or to the right, and
perhaps external places.

We can consider a bipartite graph whose vertices are all unassigned bells
and all unassigned places, and where bell x is joined to place y by an
edge if we are allowed to put bell x in place y.  _Before_ the assignments
made in the previous paragraph, this graph looks like this:

Bells:	1   2   3   4      n
|\ / \ / \ / \    /|
| X   X   X    ... |
|/ \ / \ / \ /    \|
Places:	1   2   3   4      n

This is because each internal bell is allowed to move left or right, and
bells 1 or n may also make an external place.  (In the picture, a pair of
edges cross at each "X").  However, this graph is simply a cycle of length
2n, drawn in a funny way!  The previous assignment step means that some
vertices of this graph must be deleted (a bell vertex and a place vertex
for each assignment).  To sort out the remaining bells, what we need is
precisely a perfect matching of the remaining graph.  However, since the
original graph was a cycle, the remaining graph is a collection of
disjoint paths.  It has a perfect matching precisely if every path has an
even number of vertices, and then the matching is unique, and easy to
construct.  One way involves just going around the cycle in order, ie
place 1, bell 1, place 2, bell 3, place 4,..., starting just after any
deleted vertex to get the parity right.

There is one tricky case, which is when there are _no_ places or jumps
given in the notation.  Then our graph is still the whole 2n-cycle, and
there are _two_ possible perfect matchings.  However, one of them is
forbidden by the special rule about the cross change.  So in that case we
must make sure to start matching at the right point.

That's it!  Below is a python implementation which I think works.  Depsite
the underlying simplicity, it is still quite tricky to get right.  Like
Don, I have numbered the bells (and places) 0,...,n-1.

Output
------

[3, 4] : [0, 2, 1, 3, 4, 6, 5, 7]
[] : [1, 0, 3, 2, 5, 4, 7, 6]
 : [1, 0, 2, 4, 3, 6, 5]
[(0, 2), 3] : [1, 2, 0, 3, 5, 4, 7, 6]
[(0, 6)] : [1, 2, 3, 4, 5, 6, 0]
[(0, 5), (7, 4)] : [1, 2, 3, 4, 7, 0, 5, 6]
[(1, 3), (3, 1), 2] : [0, 3, 2, 1, 5, 4, 6]

Program
-------

def jump(pn,stage):

bell,place=-1,1     # code for whether a node is a place or a bell
change=[None]*stage # change to be output
matched=set([])     # nodes that have been matched

def match(u,v):                     # match two nodes (should be a
place and a bell)
if u not in matched and v not in matched:
(s,i),(t,j)=sorted((u,v))   # put in order bell,place
change[j]=i
else:
raise Exception('Bad place notation')   # bell or place

def suc((s,i)): # successor in fixed 2n-cycle on bells and places
return (-s,max(0,min(i+s*(-1)**i,stage-1)))

for x in pn:    # match pairs given by place notation
try:
(b,p)=x
match((bell,b),(place,p))  # jump
except:
match((bell,x),(place,x))  # make place

try:
start=next(iter(matched))   # start at a matched node if there is
one
except:
start=(bell,0)              # otherwise start so as to produce
cross change

v0=start
while True:     # match remaining bells and places around the cycle
v1=suc(v0)
if not v1 in matched:   # match next pair if possible
v2=suc(v1)          # and move on by two
match(v1,v2)
v0=v2
else:                   # otherwise move by on one
v0=v1
if v0==start:           # back to where we started
break

return change

for (pn,stage) in
[([3,4],8),([],8),(,7),([(0,2),3],8),([(0,6)],7),([(0,5),(7,4)],8),([(1,3),(3,1),2],7)]:
print pn,':',jump(pn,stage)

```