Document Open Access Logo

Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time

Authors Paul Lapey, Aaron Williams

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.53.pdf
  • Filesize: 1.51 MB
  • 16 pages

Document Identifiers

Author Details

Paul Lapey
  • Department of Computer Science, Williams College, Williamstown, MA, USA
Aaron Williams
  • Department of Computer Science, Williams College, Williamstown, MA, USA

Cite AsGet BibTex

Paul Lapey and Aaron Williams. Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.53

Abstract

The number of ordered trees (also known as plane trees) with n nodes is the (n-1)st Catalan number C_{n-1}. An ordered tree can be stored directly using nodes and pointers, or represented indirectly by a Dyck word. This paper presents a loopless algorithm for generating ordered trees with n nodes using pointer-based representations. In other words, we spend 𝒪(C_{n-1})-time to generate all of the trees, and moreover, the delay between consecutive trees is worst-case 𝒪(1)-time. To achieve this run-time, each tree must differ from the previous by a constant amount. In other words, the algorithm must create a type of Gray code order. Our algorithm operates on the children of a node like a stack, by popping the first child off of one node’s stack and pushing the result onto another node’s stack. We refer to this pop-push operation as a pull, and consecutive trees in our order differ by one or two pulls. There is a simple two-case successor rule that determines the pulls to apply directly from the current tree. When converted to Dyck words, our rule corresponds to a left-shift, and these shift generate a cool-lex variant of lexicographic order. Our results represent the first pull Gray code for ordered trees, and the first fully published loopless algorithm for ordered trees using pointer representations. More importantly, our algorithm is incredibly simple: A full implementation in C, including initialization and output, uses only three loops and three if-else blocks. Our work also establishes a simultaneous Gray code for Dyck words, ordered trees, and also binary trees, using cool-lex order.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Mathematics of computing → Combinatorics
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • combinatorial generation
  • Gray code
  • simultaneous Gray code
  • ordered trees
  • plane trees
  • Dyck words
  • binary trees
  • Catalan objects
  • loopless algorithm
  • cool-lex order

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Eyal Ackerman, Gill Barequet, and Ron Y Pinter. A bijection between permutations and floorplans, and its applications. Discrete Applied Mathematics, 154(12):1674-1684, 2006. Google Scholar
  2. Jörg Arndt. Matters Computational: ideas, algorithms, source code. Springer Science & Business Media, 2010. Google Scholar
  3. Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták, Frank Ruskey, and Joe Sawada. On combinatorial generation of prefix normal words. In Symposium on Combinatorial Pattern Matching, pages 60-69. Springer, 2014. Google Scholar
  4. Jean Cardinal, Arturo Merino, and Torsten Mütze. Efficient generation of elimination trees and graph associahedra. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2128-2140. SIAM, 2022. Google Scholar
  5. Stephane Durocher, Pak Ching Li, Debajyoti Mondal, Frank Ruskey, and Aaron Williams. Cool-lex order and k-ary Catalan structures. Journal of Discrete Algorithms, 16:287-307, 2012. Google Scholar
  6. Stephane Durocher, Pak Ching Li, Debajyoti Mondal, and Aaron Williams. Ranking and loopless generation of k-ary Dyck words in cool-lex order. In International Workshop on Combinatorial Algorithms, pages 182-194. Springer, 2011. Google Scholar
  7. MC Er. Enumerating ordered trees lexicographically. The Computer Journal, 28(5):538-542, 1985. Google Scholar
  8. Frank Gray. Pulse code communication. United States Patent Number 2632058, 1953. Google Scholar
  9. Elizabeth Hartung, Hung Hoang, Torsten Mütze, and Aaron Williams. Combinatorial generation via permutation languages. i. fundamentals. Transactions of the American Mathematical Society, 375(04):2255-2291, 2022. Google Scholar
  10. Donald E Knuth. Art of Computer Programming, Volume 4, Fascicle 4, The: Generating All Trees-History of Combinatorial Generation. Addison-Wesley, 2013. Google Scholar
  11. James F Korsh and Paul LaFollette. Multiset permutations and loopless generation of ordered trees with specified degree sequence. Journal of Algorithms, 34(2):309-336, 2000. Google Scholar
  12. Paul W Lapey and Aaron Williams. Ordered tree iteration, 2022. URL: https://gitlab.com/combinatronics/ordered-tree-iteration.
  13. Paul W Lapey and Aaron Williams. A shift Gray code for fixed-content Łukasiewicz words. In International Workshop on Combinatorial Algorithms, pages 383-397. Springer, 2022. Google Scholar
  14. Joan M Lucas, Dominique Roelants van Baronaigien, and Frank Ruskey. On rotations and the generation of binary trees. Journal of Algorithms, 15(3):343-366, 1993. Google Scholar
  15. Arturo Merino and Torsten Mütze. Efficient generation of rectangulations via permutation languages. In 37th International Symposium on Computational Geometry (SoCG 2021). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021. Google Scholar
  16. Torsten Mütze. Combinatorial Gray codes-an updated survey. arXiv preprint, 2022. URL: http://arxiv.org/abs/2202.01280.
  17. Torsten Mütze. Cos++. the combinatorial object server, 2022. URL: http://combos.org.
  18. Shin-ichi Nakano. A gray code of ordered trees. arXiv preprint, 2022. URL: http://arxiv.org/abs/2207.01129.
  19. Victor Parque and Tomoyuki Miyashita. An efficient scheme for the generation of ordered trees in constant amortized time. In 2021 15th International Conference on Ubiquitous Information Management and Communication (IMCOM), pages 1-8. IEEE, 2021. Google Scholar
  20. Andrzej Proskurowski and Frank Ruskey. Binary tree Gray codes. Journal of Algorithms, 6(2):225-238, 1985. Google Scholar
  21. Frank Ruskey. Combinatorial generation. Preliminary working draft. University of Victoria, Victoria, BC, Canada, 11:20, 2003. Google Scholar
  22. Frank Ruskey and Andrzej Proskurowski. Generating binary trees by transpositions. Journal of Algorithms, 11(1):68-84, 1990. Google Scholar
  23. Frank Ruskey, Joe Sawada, and Aaron Williams. Binary bubble languages and cool-lex order. Journal of Combinatorial Theory, Series A, 119(1):155-169, 2012. Google Scholar
  24. Frank Ruskey, Joe Sawada, and Aaron Williams. De Bruijn sequences for fixed-weight binary strings. SIAM Journal on Discrete Mathematics, 26(2):605-617, 2012. Google Scholar
  25. Frank Ruskey and Aaron Williams. Generating balanced parentheses and binary trees by prefix shifts. In Proceedings of the fourteenth symposium on Computing: the Australasian theory-Volume 77, pages 107-115, 2008. Google Scholar
  26. Frank Ruskey and Aaron Williams. The coolest way to generate combinations. Discrete Mathematics, 309(17):5305-5320, 2009. Google Scholar
  27. Carla Savage. A survey of combinatorial Gray codes. SIAM review, 39(4):605-629, 1997. Google Scholar
  28. Joe Sawada and Aaron Williams. Efficient oracles for generating binary bubble languages. The electronic journal of combinatorics, pages P42-P42, 2012. Google Scholar
  29. Joe Sawada and Aaron Williams. A universal cycle for strings with fixed-content (which are also known as multiset permutations). In Workshop on Algorithms and Data Structures, pages 599-612. Springer, 2021. Google Scholar
  30. Wladyslaw Skarbek. Generating ordered trees. Theoretical Computer Science, 57(1):153-159, 1988. Google Scholar
  31. Richard P Stanley. Catalan numbers. Cambridge University Press, 2015. Google Scholar
  32. Brett Stevens and Aaron Williams. The coolest way to generate binary strings. Theory of Computing Systems, 54(4):551-577, 2014. Google Scholar
  33. Vincent Vajnovszki and Timothy Walsh. A loop-free two-close Gray-code algorithm for listing k-ary Dyck words. Journal of Discrete Algorithms, 4(4):633-648, 2006. Google Scholar
  34. D Roelants Van Baronaigien. A loopless algorithm for generating binary tree sequences. Information Processing Letters, 39(4):189-194, 1991. Google Scholar
  35. Aaron Williams. Loopless generation of multiset permutations by prefix shifts. In SODA 2009, Symposium on Discrete Algorithms, 2009. Google Scholar
  36. Aaron Williams. The greedy gray code algorithm. In Workshop on Algorithms and Data Structures, pages 525-536. Springer, 2013. Google Scholar
  37. Aaron Michael Williams. Shift Gray codes. PhD thesis, University of Victoria, 2009. Google Scholar
  38. Bo Yao, Hongyu Chen, Chung-Kuan Cheng, and Ronald Graham. Floorplan representations: Complexity and connections. ACM Transactions on Design Automation of Electronic Systems (TODAES), 8(1):55-80, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact