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

[Alexander Holroyd]

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]
[2] : [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
             matched.add(u)
             matched.add(v)
         else:
             raise Exception('Bad place notation')   # bell or place 
already assigned

     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),([2],7),([(0,2),3],8),([(0,6)],7),([(0,5),(7,4)],8),([(1,3),(3,1),2],7)]:
     print pn,':',jump(pn,stage)