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.

blog comments powered by Disqus