Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order

DOI10.1016/J.DAM.2018.09.035MaRDI QIDQ2274095zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Kung-Jui Pai, Jou-Ming Chang, Ro-Yu Wu, Shun-Chieh Chang

Publication date 19 September 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2018.09.035

zbMATH Keywords

amortized costbinary treesgeneration algorithmsleft-child sequenceslexicographic orderranking/unranking algorithms

Mathematics Subject Classification ID

Trees (05C05) Graph representations (geometric and intersection representations, etc.) (05C62) Data structures (68P05) Nonnumerical algorithms (68W05)

Recommendations

• Amortized efficiency of ranking and unranking left-child sequences in lexicographic order
• A constant amortized time algorithm for generating left-child sequences in lexicographic order
• A note on generating binary trees inA-order andB-order
• A loopless algorithm for generating multiple binary tree sequences simultaneously
• A loopless algorithm for generating multiple binary tree sequences simultaneously

Cites work

• A CAT algorithm for generating permutations with a fixed number of inversions
• A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations
• A loopless algorithm for generating binary tree sequences
• A loopless algorithm for generating multiple binary tree sequences simultaneously
• A loopless Gray code for rooted trees
• A survey in binary tree codings
• A Survey of Combinatorial Gray Codes
• Binary tree gray codes
• ECO:a methodology for the enumeration of combinatorial objects
• Enumerating, Ranking and Unranking Binary Trees
• Generating t-Ary Trees Lexicographically
• Generating Binary Trees Lexicographically
• Generating bracelets in constant amortized time
• Generating Trees and Other Combinatorial Objects Lexicographically
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 2176112 (Why is no real title available?)
• scientific article; zbMATH DE number 910896 (Why is no real title available?)
• Left distance binary tree representations
• Lexicographic generation of ordered trees
• Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
• Morphing simple polygons
• On Rotations and the Generation of Binary Trees
• On the loopless generation of binary tree sequences
• Optimal lower bounds for rank and select indexes
• Rank and select revisited and extended
• Ranking and Listing Algorithms for k-Ary Trees
• Ranking and unranking of non-regular trees with a prescribed branching sequence
• Rotation sequences and edge-colouring of binary tree pairs
• Short Note: An Efficient Implementation of Permutation Backtracking in Lexicographic Order
• Simple constant amortized time generation of fixed length numeric partitions

Cited in

(6)

• Improved algorithms for ranking and unranking \((k, m)\)-ary trees in B-order
• A loopless algorithm for generating multiple binary tree sequences simultaneously
• Amortized efficiency of ranking and unranking left-child sequences in lexicographic order
• A loopless algorithm for generating multiple binary tree sequences simultaneously
• A constant amortized time algorithm for generating left-child sequences in lexicographic order
• Gray code generation of binary trees encoded in left-child sequences

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2274095)