Joyal Bijection¶
André Joyal’s Bijection
Problem suggested by Doron Zeilberger during a talk done at CRM, Montreal, May 11th, 2012 to compare code in different languages. This is a implementation of the Joyal’s Bijection using Sage. It will not win for the most brief code, but it is object oriented, documented, reusable, testable and allows introspection.
AUTHOR:
- Sébastien Labbé, May 12th 2012
TODO:
- Base Endofunction class on sage’s FiniteSetMap classes (for both element and parent)
EXAMPLES:
Creation of an endofunction¶
sage: from slabbe import 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: from slabbe import DoubleRootedTree
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
Joyal’s bijection¶
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 got D
from f
and vice versa:
sage: D == f.to_double_rooted_tree()
True
sage: f == D.to_endofunction()
True
Endofunctions are defined on the set [0, 1, …, n-1]¶
As of now, the code supports only endofunctions defined on the set [0, 1, …, n-1]
sage: L = [1, 0, 3, 4, 5, 7, 1]
sage: f = Endofunction(L)
Traceback (most recent call last):
...
ValueError: images of [0..6] must be 0 <= i < 7
Another example¶
From a list L
, we create an endofunction f
sage: L = [12, 7, 8, 3, 3, 11, 11, 9, 5, 12, 0, 10, 9]
sage: f = Endofunction(L)
sage: f
Endofunction:
[0..12] -> [12, 7, 8, 3, 3, 11, 11, 9, 5, 12, 0, 10, 9]
From f
, we create a double rooted tree D
:
sage: D = f.to_double_rooted_tree(); D
Double rooted tree:
Edges: [(0, 12), (1, 7), (2, 8), (3, 12), (4, 3), (5, 11),
(6, 11), (7, 9), (8, 5), (10, 0), (11, 10), (12, 9)]
RootA: 9
RootB: 3
And from D
, we create an endofunction:
sage: D.to_endofunction()
Endofunction:
[0..12] -> [12, 7, 8, 3, 3, 11, 11, 9, 5, 12, 0, 10, 9]
We test that we recover the initial endofunction f
:
sage: f == f.to_double_rooted_tree().to_endofunction()
True
A random example¶
We define the set of all endofunctions on [0..7]:
sage: from slabbe import Endofunctions
sage: E = Endofunctions(8)
sage: E
Endofunctions of [0..7]
We choose a random endofunction on the set [0..7]:
sage: f = E.random_element()
sage: f # random
Endofunction:
[0..7] -> [5, 5, 0, 4, 5, 0, 1, 1]
We construct a double rooted tree from it:
sage: f.to_double_rooted_tree() # random
Double rooted tree:
Edges: [(1, 5), (2, 0), (3, 4), (4, 5), (5, 0), (6, 1), (7, 1)]
RootA: 0
RootB: 5
We recover an endofunction from the double rooted tree:
sage: f.to_double_rooted_tree().to_endofunction() # random
Endofunction:
[0..7] -> [5, 5, 0, 4, 5, 0, 1, 1]
Finally, we check the bijection:
sage: f == f.to_double_rooted_tree().to_endofunction()
True
Large random example¶
sage: E = Endofunctions(1000)
sage: f = E.random_element()
sage: f == f.to_double_rooted_tree().to_endofunction()
True
TESTS:
We test the limit cases:
sage: f = Endofunction([0])
sage: f == f.to_double_rooted_tree().to_endofunction()
True
sage: f = Endofunction([0,1])
sage: f == f.to_double_rooted_tree().to_endofunction()
True
sage: f = Endofunction([1,0])
sage: f == f.to_double_rooted_tree().to_endofunction()
True
More extensively:
sage: E = Endofunctions(1)
sage: all(f == f.to_double_rooted_tree().to_endofunction() for f in E)
True
sage: E = Endofunctions(2)
sage: all(f == f.to_double_rooted_tree().to_endofunction() for f in E)
True
sage: E = Endofunctions(3)
sage: all(f == f.to_double_rooted_tree().to_endofunction() for f in E)
True
sage: E = Endofunctions(4)
sage: all(f == f.to_double_rooted_tree().to_endofunction() for f in E)
True
TIMING TESTS:
When the extension of the file is .sage:
sage: E = Endofunctions(3)
sage: time all(f == f.to_double_rooted_tree().to_endofunction() for f in E) # not tested
True
Time: CPU 0.02 s, Wall: 0.02 s
sage: E = Endofunctions(4)
sage: time all(f == f.to_double_rooted_tree().to_endofunction() for f in E) # not tested
True
Time: CPU 0.22 s, Wall: 0.22 s
sage: E = Endofunctions(5)
sage: time all(f == f.to_double_rooted_tree().to_endofunction() for f in E) # not tested
True
Time: CPU 2.82 s, Wall: 2.82 s
sage: E = Endofunctions(6)
sage: time all(f == f.to_double_rooted_tree().to_endofunction() for f in E) # not tested
True
Time: CPU 45.66 s, Wall: 45.74 s
When the extension of the file is .spyx:
sage: E = Endofunctions(3)
sage: time all(f == f.to_double_rooted_tree().to_endofunction() for f in E) # not tested
True
Time: CPU 0.02 s, Wall: 0.02 s
sage: E = Endofunctions(4)
sage: time all(f == f.to_double_rooted_tree().to_endofunction() for f in E) # not tested
True
Time: CPU 0.21 s, Wall: 0.21 s
sage: E = Endofunctions(5)
sage: time all(f == f.to_double_rooted_tree().to_endofunction() for f in E) # not tested
True
Time: CPU 2.71 s, Wall: 2.72 s
sage: E = Endofunctions(6)
sage: time all(f == f.to_double_rooted_tree().to_endofunction() for f in E) # not tested
True
Time: CPU 44.08 s, Wall: 44.17 s
When the extension of the file is .sage:
sage: E = Endofunctions(1000)
sage: f = E.random_element()
sage: time f == f.to_double_rooted_tree().to_endofunction() # not tested
True
Time: CPU 0.09 s, Wall: 0.09 s
sage: E = Endofunctions(10000)
sage: f = E.random_element()
sage: time f == f.to_double_rooted_tree().to_endofunction() # not tested
True
Time: CPU 2.23 s, Wall: 2.24 s
When the extension of the file is .spyx:
sage: E = Endofunctions(1000)
sage: f = E.random_element()
sage: time f == f.to_double_rooted_tree().to_endofunction() # not tested
True
Time: CPU 0.11 s, Wall: 0.11 s
sage: E = Endofunctions(10000)
sage: f = E.random_element()
sage: time f == f.to_double_rooted_tree().to_endofunction() # not tested
True
Time: CPU 2.91 s, Wall: 2.93 s
-
class
slabbe.joyal_bijection.
DoubleRootedTree
(edges, rootA, rootB)¶ Bases:
object
Returns a double rooted tree.
INPUT:
edges
- list of edgesrootA
- root ArootB
- root B
EXAMPLES:
sage: from slabbe import DoubleRootedTree sage: edges = [(0,5),(1,2),(2,6),(3,2),(4,1),(5,7),(7,1),(8,2),(9,4)] sage: D = DoubleRootedTree(edges, 6, 0) sage: D Double rooted tree: Edges: [(0, 5), (1, 2), (2, 6), (3, 2), (4, 1), (5, 7), (7, 1), (8, 2), (9, 4)] RootA: 6 RootB: 0
-
graph
()¶ EXAMPLES:
sage: from slabbe import DoubleRootedTree sage: edges = [(0,5),(1,2),(2,6),(3,2),(4,1),(5,7),(7,1),(8,2),(9,4)] sage: D = DoubleRootedTree(edges, 6, 0) sage: D.graph() Graph on 10 vertices
-
skeleton
()¶ EXAMPLES:
sage: from slabbe import DoubleRootedTree sage: edges = [(0,5),(1,2),(2,6),(3,2),(4,1),(5,7),(7,1),(8,2),(9,4)] sage: D = DoubleRootedTree(edges, 6, 0) sage: D.skeleton() [0, 5, 7, 1, 2, 6]
-
skeleton_cycles
()¶ EXAMPLES:
sage: from slabbe import DoubleRootedTree sage: edges = [(0,5),(1,2),(2,6),(3,2),(4,1),(5,7),(7,1),(8,2),(9,4)] sage: D = DoubleRootedTree(edges, 6, 0) sage: D.skeleton() [0, 5, 7, 1, 2, 6] sage: D.skeleton_cycles() [(0,), (1, 5), (2, 7, 6)]
-
to_endofunction
()¶ EXAMPLES:
sage: from slabbe import DoubleRootedTree sage: edges = [(0,5),(1,2),(2,6),(3,2),(4,1),(5,7),(7,1),(8,2),(9,4)] sage: D = DoubleRootedTree(edges, 6, 0) sage: D.to_endofunction() Endofunction: [0..9] -> [0, 5, 7, 2, 1, 1, 2, 6, 2, 4]
TESTS:
sage: D = DoubleRootedTree([], 0, 0) sage: D.to_endofunction() Endofunction: [0..0] -> [0]
-
class
slabbe.joyal_bijection.
Endofunction
(L)¶ Bases:
object
Returns an endofunction.
INPUT:
L
- list of length n containing images of the integers from 0 to n-1 where the images belong to the integers from 0 to n-1.
EXAMPLES:
sage: from slabbe import Endofunction sage: L = [0, 5, 7, 2, 1, 1, 2, 6, 2, 4] sage: f = Endofunction(L) sage: f Endofunction: [0..9] -> [0, 5, 7, 2, 1, 1, 2, 6, 2, 4]
-
cycle_elements
()¶ Returns the list of all elements in a cycle for this endofunction.
OUTPUT:
list
EXAMPLES:
sage: from slabbe import Endofunction sage: L = [6, 5, 7, 2, 1, 1, 2, 6, 2, 4] sage: f = Endofunction(L) sage: f.cycle_elements() # random order [0, 6, 7, 2, 1, 5]
Note
G.cycle_basis()
is not implemented for directed or multiedge graphs (in Networkx). Hence, thecycle_basis
method is missing the 2-cycles.
-
skeleton
()¶ Return the skeleton of the endofunction.
OUTPUT:
list
EXAMPLES:
sage: from slabbe import Endofunction sage: L = [0, 5, 7, 2, 1, 1, 2, 6, 2, 4] sage: f = Endofunction(L) sage: f.skeleton() [0, 5, 7, 1, 2, 6]
-
to_double_rooted_tree
()¶ Return the double rooted tree following André Joyal Bijection.
OUTPUT:
Double rooted tree
EXAMPLES:
sage: from slabbe import Endofunction sage: L = [0, 5, 7, 2, 1, 1, 2, 6, 2, 4] sage: f = Endofunction(L) sage: f.to_double_rooted_tree() Double rooted tree: Edges: [(0, 5), (1, 2), (2, 6), (3, 2), (4, 1), (5, 7), (7, 1), (8, 2), (9, 4)] RootA: 6 RootB: 0
-
two_cycle_elements
()¶ Iterator over elements in a two-cycle.
EXAMPLES:
sage: from slabbe import Endofunction sage: L = [0, 5, 7, 2, 1, 1, 2, 6, 2, 4] sage: f = Endofunction(L) sage: list(f.two_cycle_elements()) [1, 5]
-
class
slabbe.joyal_bijection.
Endofunctions
(n)¶ Bases:
object
Returns the set of all endofunction on the set [0..n-1].
INPUT:
n
- positive integer
EXAMPLES:
sage: from slabbe import Endofunctions sage: Endofunctions(10) Endofunctions of [0..9]
-
random_element
()¶ Return a random endofunction on [0..n-1].
EXAMPLES:
sage: from slabbe import Endofunctions sage: E = Endofunctions(10) sage: E.random_element() # random Endofunction: [0..9] -> [2, 8, 7, 0, 0, 6, 2, 3, 5, 9] sage: E.random_element() # random Endofunction: [0..9] -> [8, 7, 7, 5, 4, 1, 0, 3, 8, 6]