logoalt Hacker News

Easy Random Trees

18 pointsby aebtebetenlast Tuesday at 5:08 PM2 commentsview on HN

Comments

hatthewtoday at 12:22 AM

As someone who has never heard of most of these concepts before (plane trees, catalan numbers, ballot sequences, depth vectors), I found the question "Can you think of a way to efficiently generate a random plane tree?" confusing, and I only understood the problem being solved by first trying to understand the solution. After reading through, it seems like it's asking about generating a random plane tree drawn from a uniform distribution of all possible plane trees with a given number of nodes? Cool idea once I understood it though!

vaporaviatorlablast Tuesday at 5:12 PM

Didn’t expect a few lines of APL plus ballot-sequence magic to make random plane trees feel this intuitive—super elegant construction. Curious how this could be applied in practice, e.g. generative graphics or random UI/tree structures?