My implementation of André's Joyal Bijection using Sage

## My implementation of André's Joyal Bijection using Sage

12 mai 2012 | Catégories: sage | View Comments

Doron Zeilbeger made a talk last Friday at CRM in Montreal during Sage Days 38 about $n^{n-2}$. At the end of the talk, he propoed a contest to code Joyal's Bijection which relates double rooted trees on $n$ vertices and endofunctions on $n$ elements. I wrote an implementation in Sage. My code is available here : joyal_bijection.sage. It will certainly not win for the most brief code, but it is object oriented, documented, reusable, testable and allows introspection.

# Example

First, we must load the file:

sage: load joyal_bijection.sage


Creation of an endofunction:

sage: L = [7, 0, 6, 1, 4, 7, 2, 1, 5]
sage: f = Endofunction(L)
sage: f
Endofunction:
[0..8] -> [7, 0, 6, 1, 4, 7, 2, 1, 5]


Creation of a double rooted tree:

sage: L = [(0,6),(2,1),(3,1),(4,2),(5,7),(6,4),(7,0),(8,5)]
sage: D = DoubleRootedTree(L, 1, 7)
sage: D
Double rooted tree:
Edges: [(0, 6), (2, 1), (3, 1), (4, 2), (5, 7), (6, 4), (7, 0), (8, 5)]
RootA: 1
RootB: 7


From the endofunction f, we get a double rooted tree:

sage: f.to_double_rooted_tree()
Double rooted tree:
Edges: [(0, 6), (2, 1), (3, 1), (4, 2), (5, 7), (6, 4), (7, 0), (8, 5)]
RootA: 1
RootB: 7


From the double rooted tree D, we get an endofunction:

sage: D.to_endofunction()
Endofunction:
[0..8] -> [7, 0, 6, 1, 4, 7, 2, 1, 5]


In fact, we get D from f and vice versa:

sage: D == f.to_double_rooted_tree()
True
sage: f == D.to_endofunction()
True


# Timing

On my machine, it takes 2.23 seconds to transform a random endofunction on $\{0, 1, \cdots, 9999\}$ to a double rooted tree and then back to the endofunction and make sure the result is OK:

sage: E = Endofunctions(10000)
sage: f = E.random_element()
sage: time f == f.to_double_rooted_tree().to_endofunction()
True
Time: CPU 2.23 s, Wall: 2.24 s