`even_permutation`#

Even permutations

We call even permutation, a permutation on the set of even size X_n = {-n, -n+1, ldots, n-1}. The set X_n comes with a canonical involution without fixed points i mapsto -i-1 (note that -i-1 is the bit complement to i). The commutator of this canonical involution are the signed permutations.

surface_dynamics.misc.even_permutation.even_perm_canonical_label(p)#

Canonical label for the permutation p assuming that together with the canonical involution it acts transitively on X_n = {-n, -n+1, ldots, n-1}.

For fatgraphs, we use canonical labelings for the faces, so that canonical labels detect the orientable fatgraphs.

For the possible starting points, we only need to consider the ones that have one side in the largest and the other side in the smallest possible. For now, we run through all possibilities.

OUTPUT: a pair (canonical_p, map)

EXAMPLES:

sage: from surface_dynamics.misc.even_permutation import (even_perm_check,
....:    even_perm_canonical_label, even_perm_is_transitive, even_perm_relabel,
....:    signed_permutations, even_perm_tilde)
sage: from array import array

sage: def test_perm(p):
....:     p = array('l', p)
....:     even_perm_check(p)
....:     n = len(p) // 2
....:     assert even_perm_is_transitive(p)
....:     c = even_perm_canonical_label(p)[0]
....:     q = even_perm_tilde(p)
....:     cc = even_perm_canonical_label(q)[0]
....:     assert c == cc, (c, cc)
....:     for q in signed_permutations(n):
....:         pp = even_perm_relabel(p, q)
....:         cc, mm = even_perm_canonical_label(pp)
....:         assert cc == even_perm_relabel(pp, mm)
....:         assert c == cc, (q, pp, cc)

sage: test_perm([-2,0,1,-1,2,-3])
sage: test_perm([-2,0,1,2,-1,-3])
sage: test_perm([2,1,0,-1,-3,-2])
sage: test_perm([2,0,1,-1,-3,-2])

sage: test_perm([2,0,-4,1,-1,-3,-2,3])
sage: test_perm([0,2,1,3,-2,-1,-4,-3])

surface_dynamics.misc.even_permutation.even_perm_canonical_label_from(p, i)#

Return canonical labels for p that starts at i.

INPUT:

p – even permutation
i – integer in X_n = {-n, -n+1, ldots, n-1}

OUTPUT: a signed permutation that specifies the new labels

EXAMPLES:

sage: from array import array
sage: from surface_dynamics.misc.even_permutation import (even_perm_canonical_label_from,
....:     is_signed_perm)

sage: p = array('l', [-1, 2, 0, 1, -3, -2])
sage: even_perm_canonical_label_from(p, 0)
array('l', [0, -2, -3, 2, 1, -1])

sage: p = array('l', [1, 2, 0, -2, -1, -3])
sage: is_signed_perm(even_perm_canonical_label_from(p, 0))
True

sage: p = array('l', [2,1,0,-1,-3,-2])
sage: even_perm_canonical_label_from(p, 1)
array('l', [2, 0, 1, -2, -1, -3])

surface_dynamics.misc.even_permutation.even_perm_check(p)#

EXAMPLES:

sage: from surface_dynamics.misc.even_permutation import even_perm_check
sage: even_perm_check([0, 1, 2, -3, -2, -1])
sage: even_perm_check([0])
Traceback (most recent call last):
...
ValueError: odd length

sage: even_perm_check([-2,0])
Traceback (most recent call last):
...
ValueError: element -2 at position 0 out of range

sage: even_perm_check([0,1,-2,0])
Traceback (most recent call last):
...
ValueError: element 0 repeated

surface_dynamics.misc.even_permutation.even_perm_compose(p1, p2)#

Return the composition of p1 and p2

EXAMPLES:

sage: from surface_dynamics.misc.even_permutation import even_perm_compose

sage: p1 = [0, -1, 2, -3, 1, -2]
sage: p2 = [-1, 0, -2, 1, -3, 2]
sage: q = even_perm_compose(p1, p2)
sage: q
array('l', [-1, 2, -2, 1, 0, -3])
sage: p2[p1[3]] == q[3]
True

surface_dynamics.misc.even_permutation.even_perm_compose_i(p1, p2)#

Return the compositions of the inverses of p1 and p2

EXAMPLES:

sage: from surface_dynamics.misc.even_permutation import (even_perm_compose,
....:      even_perm_invert, even_perm_compose_i)
sage: p1 = [0, -2, 2, 1, -1, -3]
sage: p2 = [1, -1, -2, -3, 2, 0]
sage: even_perm_compose_i(p1, p2)
array('l', [-1, -3, -2, 1, 0, 2])
sage: even_perm_compose(even_perm_invert(p1), even_perm_invert(p2))
array('l', [-1, -3, -2, 1, 0, 2])

surface_dynamics.misc.even_permutation.even_perm_cycles(p)#

EXAMPLES:

sage: from surface_dynamics.misc.even_permutation import even_perm_cycles

sage: even_perm_cycles([-1,0])
([(-1, 0)], [0, 0])
sage: even_perm_cycles([-1,0,-2,1])
([(-2,), (-1, 1, 0)], [1, 1, 0, 1])

surface_dynamics.misc.even_permutation.even_perm_identity(n)#

Return the identity

EXAMPLES:

sage: from surface_dynamics.misc.even_permutation import even_perm_identity

sage: even_perm_identity(3)
array('l', [0, 1, 2, -3, -2, -1])
sage: even_perm_identity(0)
array('l')

surface_dynamics.misc.even_permutation.even_perm_init(data)#

surface_dynamics.misc.even_permutation.even_perm_invert(p)#

Return the inverse of p.

EXAMPLES:

sage: from surface_dynamics.misc.even_permutation import (even_perm_invert,
....:    even_perm_compose, even_perm_identity)

sage: p = [-2,0,-1,1]
sage: q = even_perm_invert(p)
sage: q
array('l', [1, -1, 0, -2])
sage: even_perm_compose(p,q)
array('l', [0, 1, -2, -1])
sage: even_perm_compose(q,p)
array('l', [0, 1, -2, -1])

sage: for _ in range(10):
....:     n = randint(1, 20)
....:     p = list(range(-n, n))
....:     shuffle(p)
....:     q = even_perm_invert(p)
....:     assert even_perm_compose(p, q) == even_perm_compose(q, p) == even_perm_identity(n)

surface_dynamics.misc.even_permutation.even_perm_is_orientable(p)#

Test whether the permutation is orientable (that is do not mix non-negatives with negatives)

EXAMPLES:

sage: from surface_dynamics.misc.even_permutation import even_perm_is_orientable
sage: even_perm_is_orientable([1,0,-1,-2])
True
sage: even_perm_is_orientable([0,1,-2,-1])
True
sage: even_perm_is_orientable([1,-1,0,-2])
False

surface_dynamics.misc.even_permutation.even_perm_is_transitive(p)#

EXAMPLES:

sage: from array import array
sage: from surface_dynamics.misc.even_permutation import even_perm_is_transitive

sage: p = array('l', [0, 1, -2, -1])
sage: even_perm_is_transitive(p)
False
sage: p = array('l', [0, 1, -1, -2])
sage: even_perm_is_transitive(p)
True

sage: from itertools import permutations
sage: for p in permutations((-2,-1,0,1)):
....:     print("%s %s" % (p, even_perm_is_transitive(array('l',p))))
(-2, -1, 0, 1) True
(-2, -1, 1, 0) True
(-2, 0, -1, 1) True
(-2, 0, 1, -1) True
(-2, 1, -1, 0) True
(-2, 1, 0, -1) True
(-1, -2, 0, 1) True
(-1, -2, 1, 0) False
(-1, 0, -2, 1) True
(-1, 0, 1, -2) True
(-1, 1, -2, 0) False
(-1, 1, 0, -2) True
(0, -2, -1, 1) True
(0, -2, 1, -1) False
(0, -1, -2, 1) True
(0, -1, 1, -2) True
(0, 1, -2, -1) False
(0, 1, -1, -2) True
(1, -2, -1, 0) True
(1, -2, 0, -1) True
(1, -1, -2, 0) True
(1, -1, 0, -2) True
(1, 0, -2, -1) True
(1, 0, -1, -2) True

surface_dynamics.misc.even_permutation.even_perm_minus(n)#

EXAMPLES:

sage: from surface_dynamics.misc.even_permutation import even_perm_minus
sage: even_perm_minus(2)
array('l', [-1, -2, 1, 0])

surface_dynamics.misc.even_permutation.even_perm_relabel(p, m)#

Relabel (= conjugate) the permutation p according to m.

INPUT:

p - a list of even permutations
m - a permutation

EXAMPLES:

sage: from surface_dynamics.misc.even_permutation import (even_perm_relabel,
....:      even_perm_identity, even_perm_tilde)
sage: even_perm_relabel([-1, 0, -2, 1], [1, 0, -2, -1])
array('l', [1, -1, -2, 0])

sage: from array import array
sage: p = array('l', [1, -2, 0, -1])
sage: even_perm_relabel(p, even_perm_identity(2)) == p
True

sage: from surface_dynamics.misc.even_permutation import signed_permutations
sage: p = array('l', [-2,0,1,2,-1,-3])
sage: for s in signed_permutations(3):
....:     p1 = even_perm_relabel(even_perm_tilde(p), s)
....:     p2 = even_perm_tilde(even_perm_relabel(p, s))
....:     assert p1 == p2

surface_dynamics.misc.even_permutation.even_perm_tilde(p)#

EXAMPLES:

sage: from surface_dynamics.misc.even_permutation import even_perm_tilde
sage: even_perm_tilde([1r, 0r, -1r, -2r])
array('l', [1, 0, -1, -2])
sage: even_perm_tilde([1r, -1r, -2r, 0r])
array('l', [-1, 1, 0, -2])

sage: from surface_dynamics.misc.even_permutation import even_permutations, is_signed_perm
sage: all((p == even_perm_tilde(p)) == is_signed_perm(p) for p in even_permutations(3))
True

surface_dynamics.misc.even_permutation.even_permutations(n)#

surface_dynamics.misc.even_permutation.is_signed_perm(p)#

surface_dynamics.misc.even_permutation.signed_permutations(n)#

EXAMPLES:

sage: from surface_dynamics.misc.even_permutation import signed_permutations
sage: for p in signed_permutations(2):
....:     assert p[0r] == ~p[~0r]
....:     assert p[1r] == ~p[~1r]

even_permutation

Contents

even_permutation#

`even_permutation`#