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