Stamp Foldings, Semi-Meanders, and Open Meanders: Fast Generation Algorithms

Joe Sawada, Roy Li


By considering a permutation representation for  stamp-foldings and semi-meanders we construct tree-like data structures that will allow us to generate these objects in constant amortized time.  Additionally, by maintaining the wind-factor and applying an additional optimization, the algorithm for semi-meanders can be modified to produce the fastest known algorithm to generate open meanders.


Stamp folding; Semi-meander; Meander; CAT algorithm; Permutation

Full Text: