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

  • Joe Sawada
  • Roy Li
Keywords: Stamp folding, Semi-meander, Meander, CAT algorithm, Permutation


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.
Article Number