Improving the Florentine algorithms: recovering algorithms for Motzkin and Schr\"oder paths

Axel Bacher

arxiv: 1802.06030 · v2 · pith:TPXXWUVInew · submitted 2018-02-16 · 💻 cs.DS · math.CO

Improving the Florentine algorithms: recovering algorithms for Motzkin and Schr\"oder paths

Axel Bacher This is my paper

classification 💻 cs.DS math.CO

keywords algorithmsflorentinepathsmotzkinoderrejectionschrachieve

0 comments

read the original abstract

We present random sampling procedures for Motzkin and Schr\"oder paths, following previous work on Dyck paths. Our algorithms follow the anticipated rejection method of the Florentine algorithms (Barcucci et al. 1994+), but introduce a recovery idea to greatly reduce the probability of rejection. They use an optimal amount of randomness and achieve a better time complexity than the Florentine algorithms.

This paper has not been read by Pith yet.

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Leap generators for composition schemes
math.CO 2026-05 unverdicted novelty 7.0

Leap generators for supercritical composition schemes C = A ∘ B yield linear-time exact-size samplers whose output distribution on size-n objects has total variation distance (c + o(1)) n^{-1/2} from uniform.