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

DOI10.1007/978-3-319-48749-6_37MaRDI QIDQ2958342zbMATH OpenOpenAlexFDO

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

Publication date 1 February 2017

Published in Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-48749-6_37

zbMATH Keywords

binary treeslexicographic orderranking algorithmsamortized costleft-child sequencesunranking algorithms

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Data structures (68P05) Nonnumerical algorithms (68W05)

Recommendations

• Amortized efficiency of generation, 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
• Ranking and Unranking of AVL-Trees
• A loopless algorithm for generating multiple binary tree sequences simultaneously

Cites work

• scientific article; zbMATH DE number 2176112 (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 Gray code for rooted trees
• A loopless algorithm for generating binary tree sequences
• A loopless algorithm for generating multiple binary tree sequences simultaneously
• A survey in binary tree codings
• Binary tree gray codes
• Efficient loopless generation of Gray codes for \(k\)-ary trees.
• Enumerating, Ranking and Unranking Binary Trees
• Generating t-Ary Trees Lexicographically
• Generating Trees and Other Combinatorial Objects Lexicographically
• Generating bracelets in constant amortized time
• Left distance binary tree representations
• Lexicographic generation of ordered trees
• Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
• 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
• Short Note: An Efficient Implementation of Permutation Backtracking in Lexicographic Order

Cited in

(2)

• Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order
• A Constant Amortized Time Algorithm for Generating Left-Child Sequences in Lexicographic Order

This page was built for publication: Amortized efficiency of 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 Q2958342)