Thursday, March 8, 2018

Tabular method for finding shuffle-greedy growth sequences from undip words

Tabular calculation of a shuffle-greedy growth sequence for a tetrahedron.
Given an undip word (i.e., a shuffle of two Dyck words coded in four alphabetic characters representing a dichotomy of style—open/closed—and a dichotomy of polarity—up/down: u, n, d, p) describing a triangulated surface with a Hamiltonian dual, there is a simple tabular method to find a 'shuffle-greedy' growth sequence for that triangulated surface. (The growth sequence is 'shuffle-greedy' in the sense that every shuffle edit will be performed as soon as it becomes possible.)

Tabular procedure to find a shuffle-greedy growth sequence from an undip word:
Write out the undip word at the top of the page, and draw the two sets of non-crossing arcs that connect paired letters in its up-Dyck word and in its down-Dyck word. 
Under the word, grid out a table with one column for each letter in the undip word, plus one more column at the left for the root mark, '|', which is crossed at the beginning of each orbit of the Hamilton circuit.
An arc is termed outermost if it has no active arc enclosing it. (Initially all arcs are active.) 
A letter is termed recorded if it has already been entered in its column in the table.

Begin at the root mark '|' in the first row. 
1.  Proceed rightward in the row looking for an open letter in the undip word that starts an outermost arc. For each recorded letter passed over in this search, enter a dot in the table. 
2. Upon finding an open letter that starts an outermost arc, record that letter in the table in its column, and proceed to its paired closed letter, and enter that letter in the table in its column. For each recorded letter the arc has skipped over (all skipped letters will, necessarily, be of the other polarity since none of the contained arcs of the same polarity have recorded) enter an 's' in the table. Finally, mark the arc inactive and proceed rightward from the closed letter and... 
Repeat step 1. 
Upon reaching the end of a row, continue at the root mark '|' in the row below. 
Suppress any trail of dots that goes to the end of the row, because the next root bar '|' makes this positional information redundant. 
Continue until all letters have been recorded. 
The growth sequence is now described by the characters in the table read in the usual way (left-to-right, top-to-bottom,) but with the closed characters, 'd' and 'p', suppressed.

Tabular calculation of a shuffle-greedy growth sequence for a cube.


Tabular calculation of a shuffle-greedy growth sequence for a dodecahedron.

The growth sequence has as many stages as the growth sequence code has alphabetic letters in the growth code (= non-closed alphabetic letters in the table.)

The number of growth stages does not seem to grow excessively with undip word length:

Tetrahedron, 4 letters in undip word, 3 growth stages.
Cube, 8 letters in undip word, 8 growth stages.
Dodecahedron, 20 letters in undip word, 29 growth stages.

[At this point I am switching to using a forward slash as the root mark as that character is available in monospace fonts and is never confused with an el.]

Growth sequence code for undp tetrahedron: /u/.ns
Growth stages for undp tetrahedron: 
ud
unpd
undp


Growth sequence code for nnuuppdd cube: /n/.n/..uss/...uss
Growth stages for nnuuppdd cube:
np
nnpp
nnudpp
nnupdp
nnuppd
nnuudppd
nnuupdpd
nnuuppdd

[At this point I am replacing runs of dots with the integer number of dots.]

Growth sequence code for unnndnunuuupppdpdpdd dodecahedron:

/uu/1nss/2nss/3nss/5ns/7n/8usssss/9ussss/10usss

Growth stages for unnndnunuuupppdpdpdd dodecahedron:

ud
udud
unpdud
undpud
undupd
unnpdupd
unndpupd
unnduppd
unnnpduppd
unnndpuppd
unnndupppd
unnndnpupppd
unnndnuppppd
unnndnunpppppd
unnndnunudpppppd
unnndnunupdppppd
unnndnunuppdpppd
unnndnunupppdppd
unnndnunuppppdpd
unnndnunupppppdd
unnndnunuudpppppdd
unnndnunuupdppppdd
unnndnunuuppdpppdd
unnndnunuupppdppdd
unnndnunuuppppdpdd
unnndnunuuudppppdpdd
unnndnunuuupdpppdpdd
unnndnunuuuppdppdpdd
unnndnunuuupppdpdpdd




No comments:

Post a Comment