A constant amortized time algorithm for generating left-child sequences in lexicographic order

DOI10.1007/978-3-319-59605-1_20MaRDI QIDQ4632217zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 26 April 2019

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-59605-1_20

zbMATH Keywords

binary treeslexicographic ordergeneration algorithmsamortized costleft-child sequencesconstant-amortized-time algorithm

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Algorithms on strings (68W32)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 2176112 (Why is no real title available?)
• scientific article; zbMATH DE number 910896 (Why is no real title available?)
• A CAT algorithm for generating permutations with a fixed number of inversions
• A Survey of Combinatorial Gray Codes
• 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 survey in binary tree codings
• Amortized efficiency of ranking and unranking left-child sequences in lexicographic order
• Binary tree gray codes
• Enumerating, Ranking and Unranking Binary Trees
• Generating Binary Trees Lexicographically
• Generating Trees and Other Combinatorial Objects Lexicographically
• Generating bracelets in constant amortized time
• 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
• Rotation sequences and edge-colouring of binary tree pairs
• Simple constant amortized time generation of fixed length numeric partitions

Cited in

(5)

• Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order
• Amortized efficiency of ranking and unranking left-child sequences in lexicographic order
• A linear time algorithm for binary tree sequences transformation using left-arm and right-arm rotations
• A loopless algorithm for generating multiple binary tree sequences simultaneously
• A loopless algorithm for generating multiple binary tree sequences simultaneously

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: A constant amortized time algorithm for generating 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 Q4632217)