FromPermutation

The increasing binary tree built by minimum-splitting recursion: the position of the smallest value roots the tree, everything before it recurses to the left, everything after it to the right.

FromPermutation(Permutation)The increasing binary tree built by minimum-splitting recursion: the position of the smallest value roots the tree, everything before it recurses to the left, everything after it to the right.

Typed signatures

Type	Package	Applies
(permutation) -> increasing_binary_tree	combinatorics	always

Domain: Combinatorial maps

Details

• Takes a Permutation and returns a IncreasingBinaryTree — a typed map, so a wrong carrier is a type error rather than a wrong answer.
• Paired with ToPermutation, whose overload set (IncreasingBinaryTree among others) names this map's codomain. The root is always 1: every permutation of [n] holds the value 1, and heap order puts the global minimum at the top regardless of which permutation it came from. Built by real recursion, the same [label, left, right] nesting IncreasingBinaryTrees' cartesianTree builds.

Examples

Basic #

the one-line word $231$

live ↗

In$\mathrm{FromPermutation}({\operatorname{Permutation}}([2, 3, 1]))$Out${\operatorname{IncreasingBinaryTree}}(\bigl\lbrack1, \bigl\lbrack2, 0, \bigl\lbrack3, 0, 0\bigr\rbrack\bigr\rbrack, 0\bigr\rbrack)$

About

Examples	1