## 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

# Comments

I am using the Sage graph library (Networkx) to find the cycles of a graph and to find the shortest path between two vertices. It would be interesting to compare the timing when using the zen library which is lot faster then networkx.