SpringerLink
Log in

Generating Cyclic Rotation Gray Codes for Stamp Foldings and Semi-meanders

  • Conference paper
  • First Online:
Combinatorial Algorithms (IWOCA 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13889))

Included in the following conference series:

  • 403 Accesses

Abstract

We present a simple algorithm that generates cyclic rotation Gray codes for stamp foldings and semi-meanders, where consecutive strings differ by a stamp rotation. These are the first known Gray codes for stamp foldings and semi-meanders, and we thus solve an open problem posted by Sawada and Li in [Electron. J. Comb. 19(2), 2012]. The algorithm generates each stamp folding and semi-meander in constant amortized time and O(n)-amortized time per string respectively, using a linear amount of memory.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 64.19
Price includes VAT (Germany)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 80.24
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Bobier, B., Sawada, J.: A fast algorithm to generate open meandric systems and meanders. ACM Trans. Algorithms 6(2), 1–12 (2010)

    Article  MathSciNet  Google Scholar 

  2. COS++. The combinatorial object server (2023): Generate meanders and stamp foldings (2023)

    Google Scholar 

  3. France, M., van der Poorten, A.: Arithmetic and analytic properties of paper folding sequences. Bull. Aust. Math. Soc. 24(1), 123–131 (1981)

    Article  MathSciNet  Google Scholar 

  4. Hoffmann, K., Mehlhorn, K., Rosenstiehl, P., Tarjan, R.: Sorting Jordan sequences in linear time using level-linked search trees. Inf. Control 68(1), 170–184 (1986)

    Article  MathSciNet  Google Scholar 

  5. Iordache, O.: Implementing Polytope Projects for Smart Systems, pp. 65–80. Springer, Cham (2017). Conditioned walks

    Google Scholar 

  6. Jensen, I.: A transfer matrix approach to the enumeration of plane meanders. J. Phys. A: Math. Gen. 33(34), 5953 (2000)

    Article  MathSciNet  Google Scholar 

  7. Koehler, J.: Folding a strip of stamps. J. Comb. Theory 5(2), 135–152 (1968)

    Article  MathSciNet  Google Scholar 

  8. Legendre, S.: Foldings and meanders. Australas. J Comb. 58, 275–291 (2014)

    MathSciNet  Google Scholar 

  9. Li, Y., Sawada, J.: Gray codes for reflectable languages. Inf. Process. Lett. 109(5), 296–300 (2009)

    Article  MathSciNet  Google Scholar 

  10. Lucas, E.: Théorie des Nombres, vol. 1, p. 120. Gauthier-Villars, Paris (1891)

    Google Scholar 

  11. Lunnon, W.: A map-folding problem. Math. Comput. 22, 193–199 (1968)

    Article  MathSciNet  Google Scholar 

  12. Mütze, T.: Combinatorial Gray codes - an updated survey. ar**v preprint ar**v:2202.01280 (2022)

  13. OEIS Foundation Inc., The on-line encyclopedia of integer sequences, published electronically at (2023). http://oeis.org

  14. Sainte-Lagüe, M.: Avec des nombres et des lignes, pp. 147–162. Vuibert, Paris (1937)

    Google Scholar 

  15. Sawada, J., Li, R.: Stamp foldings, semi-meanders, and open meanders: fast generation algorithms. Electron. J. Comb. 19(2), 43 (2012)

    Article  MathSciNet  Google Scholar 

  16. Sawada, J., Williams, A., Wong, D.: Inside the binary reflected Gray code: Flip-swap languages in 2-Gray code order. In: Lecroq, T., Puzynina, S. (eds.) WORDS 2021. LNCS, vol. 12847, pp. 172–184. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-85088-3_15

    Chapter  Google Scholar 

  17. Sawada, J., Williams, A., Wong, D.: Flip-swap languages in binary reflected Gray code order. Theor. Comput. Sci. 933, 138–148 (2022)

    Article  MathSciNet  Google Scholar 

  18. Schweitzer-Stenner, R., Uversky, V.: Protein and peptide folding, misfolding, and non-folding. Wiley Series in Protein and Peptide Science. Wiley, Hoboken (2012)

    Google Scholar 

  19. Sloane, N.: A Handbook of Integer Sequences. MIT Press, Cambridge (1973)

    Google Scholar 

  20. Touchard, J.: Contribution a létude du probleme des timbres poste. Can. J. Math. 2, 385–398 (1950)

    Article  MathSciNet  Google Scholar 

  21. Zhu, L., Yao, S., Li, B., Song, A., Jia, Y., Mitani, J.: A geometric folding pattern for robot coverage path planning. In: 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 8509–8515 (2021)

    Google Scholar 

Download references

Acknowledgements

This research is supported by the Macao Polytechnic University research grant (Project code: RP/FCA-02/2022) and the National Research Foundation of Korea (NRF) grant funded by the Ministry of Science and ICT (MSIT), Korea (No. 2020R1F1A1A01070666).

Author information

Authors and Affiliations

  1. Macao Polytechnic University, Macao, China

    Bowie Liu & Dennis Wong

Authors
  1. Bowie Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Dennis Wong
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Dennis Wong .

Editor information

Editors and Affiliations

  1. National Cheng Kung University, Tainan, Taiwan

    Sun-Yuan Hsieh

  2. National Taipei University of Business, Taoyuan, Taiwan

    Ling-Ju Hung

  3. National Taitung University, Taitung, Taiwan

    Chia-Wei Lee

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Liu, B., Wong, D. (2023). Generating Cyclic Rotation Gray Codes for Stamp Foldings and Semi-meanders. In: Hsieh, SY., Hung, LJ., Lee, CW. (eds) Combinatorial Algorithms. IWOCA 2023. Lecture Notes in Computer Science, vol 13889. Springer, Cham. https://doi.org/10.1007/978-3-031-34347-6_23

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-34347-6_23

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-34346-9

  • Online ISBN: 978-3-031-34347-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation