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 edges
  • rootA - root A
  • rootB - 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, the cycle_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]