permutation

Permutations and partial permutations on {0, 1, …, n-1}.

Permutation are implemented as lists of integers (where -1 represents an element which is unset).

class surface_dynamics.misc.permutation.PermutationGroupOrbit(n, gens, S=None, check=True)

Dynamical orbit generation.

This is to be used when computing the automorphism group of an object (e.g. a ribbon graph). It allows to iterate through orbit representatives dynamically (i.e. group generators can be added on the fly).

EXAMPLES:

sage: from surface_dynamics.misc.permutation import PermutationGroupOrbit
sage: P1 = PermutationGroupOrbit(7, ['(0,1)', '(0,1,2,3,4,5,6)'])
sage: P2 = PermutationGroupOrbit(4, ['(0,1)', '(2,3)'])

add_generator(g, check=True)

EXAMPLES:

sage: from surface_dynamics.misc.permutation import PermutationGroupOrbit

sage: O = PermutationGroupOrbit(4, [])
sage: next(O)
0
sage: O.add_generator('(0,1)(2,3)')
sage: next(O)
2
sage: next(O)
Traceback (most recent call last):
...
StopIteration

gens()

group_cardinality()

EXAMPLES:

sage: from surface_dynamics.misc.permutation import PermutationGroupOrbit
sage: PermutationGroupOrbit(7, []).group_cardinality()
1
sage: PermutationGroupOrbit(5, ['(0,2)(3,4)']).group_cardinality()
2
sage: PermutationGroupOrbit(7, ['(0,1)', '(0,1,2,3,4,5,6)']).group_cardinality()
5040

libgap_group()

next()

num_gens()

reset_iterator(S=None)

Reset the set we iterate over with this group.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import PermutationGroupOrbit

sage: O = PermutationGroupOrbit(4, [])
sage: list(O)
[0, 1, 2, 3]
sage: list(O)
[]
sage: O.reset_iterator()
sage: list(O)
[0, 1, 2, 3]
sage: list(O)
[]

sage: O.add_generator('(0,1)(2,3)')
sage: list(O)
[]
sage: O.reset_iterator()
sage: list(O)
[0, 2]

surface_dynamics.misc.permutation.argmin(l)

Return the position of the minimal element in the list l.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import argmin
sage: argmin([3,0,1,2])
1
sage: argmin([-1,3,5,-2,50])
3

surface_dynamics.misc.permutation.canonical_perm(part, i=0)

Return the canonical permutation with the given part.

EXAMPLES:

sage: from surface_dynamics.flat_surfaces.separatrix_diagram import canonical_perm
sage: canonical_perm([3,2])
[1, 2, 0, 4, 3]
sage: canonical_perm([2,2,2])
[1, 0, 3, 2, 5, 4]
sage: canonical_perm([1,1,3])
[0, 1, 3, 4, 2]

surface_dynamics.misc.permutation.canonical_perm_i(part, i=0)

Return the canonical permutation reversed.

EXAMPLES:

sage: from surface_dynamics.flat_surfaces.separatrix_diagram import canonical_perm_i
sage: canonical_perm_i([3,2])
[2, 0, 1, 4, 3]
sage: canonical_perm_i([2,2,2])
[1, 0, 3, 2, 5, 4]
sage: canonical_perm_i([1,1,3])
[0, 1, 4, 2, 3]

surface_dynamics.misc.permutation.constellation_init(vertices, edges, faces, n=None, check=True)

Each of vertices, edges or faces can be ``None, an integer or an object to initialize a (partial) permutation.

INPUT:

• vertices, edges, faces - permutations given as strings or lists

• n - (optional) number of darts

• check - boolean default True

TESTS:

sage: from surface_dynamics.misc.permutation import constellation_init

sage: constellation_init([0,1], [1,0], [1,0])
[[0, 1], [1, 0], [1, 0]]
sage: constellation_init([0r,1r], [1r,0r], [1r,0r])
[[0, 1], [1, 0], [1, 0]]

sage: constellation_init([2,1,0], [1,2,0], None)
[[2, 1, 0], [1, 2, 0], [0, 2, 1]]

sage: constellation_init(3, 2, None, 6)
[[1, 2, 0, 4, 5, 3], [1, 0, 3, 2, 5, 4], [0, 2, 5, 1, 4, 3]]

sage: constellation_init('(0,1)', '(0,1)', '()')
[[1, 0], [1, 0], [0, 1]]

sage: constellation_init('(0,2,3,6)(1,4,5,7)', None, None)
[[2, 4, 3, 6, 5, 7, 0, 1], [1, 0, 3, 2, 5, 4, 7, 6], [7, 6, 2, 0, 4, 1, 5, 3]]

Each number (including fixed point) should be specified otherwise they are just ignored:

sage: constellation_init('(1,6,5)(2,3,4)', '(1,2)(3,4)(5,6)', '(1,4,2,5)(3)(6)')
[[-1, 6, 3, 4, 2, 1, 5], [-1, 2, 1, 4, 3, 6, 5], [-1, 4, 5, 3, 2, 1, 6]]

TESTS:

sage: constellation_init(None, '(0,1)(2,3)(4,5)', '(0,2,4)(1)(3,5)')
[[5, 0, 1, 4, 3, 2], [1, 0, 3, 2, 5, 4], [2, 1, 4, 5, 0, 3]]
sage: constellation_init([-1,-1,2,3], None, [-1,-1,3,2])
[[-1, -1, 2, 3], [-1, -1, 3, 2], [-1, -1, 3, 2]]
sage: constellation_init([-1,-1,2,3], 2, [-1,-1,3,2])
[[-1, -1, 2, 3], [-1, -1, 3, 2], [-1, -1, 3, 2]]
sage: constellation_init(None, 2, [-1,-1,3,2])
[[-1, -1, 2, 3], [-1, -1, 3, 2], [-1, -1, 3, 2]]
sage: constellation_init([-1,-1,2,3], 2, None)
[[-1, -1, 2, 3], [-1, -1, 3, 2], [-1, -1, 3, 2]]
sage: constellation_init([1, 4, -1, -1, 5, 0], None, None)
[[1, 4, -1, -1, 5, 0], [1, 0, -1, -1, 5, 4], [0, 5, -1, -1, 4, 1]]

surface_dynamics.misc.permutation.cycles_to_list(t, n=None, partial=False)

Returns a permutation on [0, n-1] from a list of cycles on [0, n-1]

EXAMPLES:

sage: from surface_dynamics.misc.permutation import cycles_to_list

sage: cycles_to_list([[1,3,5]])
[0, 3, 2, 5, 4, 1]
sage: cycles_to_list([[1,3,5]], partial=True)
[-1, 3, -1, 5, -1, 1]

sage: cycles_to_list([[1,3,5],[0,2,4],[6]])
[2, 3, 4, 5, 0, 1, 6]

sage: cycles_to_list([])
[]
sage: cycles_to_list([[],[]])
[]

sage: cycles_to_list([[1,4,2,5],[3],[6]], partial=True)
[-1, 4, 5, 3, 2, 1, 6]

sage: cycles_to_list([[0,5]], 3)
Traceback (most recent call last):
...
ValueError: cycle value out of range

surface_dynamics.misc.permutation.equalize_perms(l)

Extend the permutations in l to have the same lengths.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import equalize_perms
sage: li = [[0, 1], [2, 1, 0]]
sage: equalize_perms(li)
3

surface_dynamics.misc.permutation.perm_base64_str(p, n=None)

Make a canonical ASCII string out of p.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_base64_str, perm_from_base64_str
sage: from array import array

sage: perm_base64_str([])
''
sage: perm_base64_str([3,1,0,2])
'3102'
sage: s = perm_base64_str(range(2048))
sage: s
'00010203...v+v-'
sage: perm_from_base64_str(s, 2048) == list(range(2048))
True

surface_dynamics.misc.permutation.perm_check(l, n=None)

Checks that l is a partial permutation of {0, 1, …, n-1}.

INPUT:

• n - integer (optional)

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_check

Good permutations:

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

sage: perm_check([1,0,-1,-1,-1], 2)
True

sage: perm_check([0,-1])
True
sage: perm_check([-1,1])
True

Bad permutations:

sage: perm_check([1, 0, 3, 2], 3)
False
sage: perm_check([2, 0])
False
sage: perm_check([1, 0, 1])
False

sage: perm_check([1,-1])
False
sage: perm_check([-1,0])
False

surface_dynamics.misc.permutation.perm_commutator(p1, p2, n=None)

Return the commutator ~p1 ~p2 p1 p2.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_commutator, perm_compose, perm_compose_i

sage: p1 = [1, 2, 0, 3]
sage: p2 = [0, 3, 1, 2]
sage: perm_commutator(p1, p2)
[2, 3, 0, 1]
sage: perm_compose(perm_compose_i(p1, p2), perm_compose(p1, p2))
[2, 3, 0, 1]

sage: p1 = [3, 2, 0, 5, 1, 4]
sage: p2 = [5, 2, 1, 0, 4, 3]
sage: perm_commutator(p1, p2)
[1, 2, 5, 3, 0, 4]
sage: perm_compose(perm_compose_i(p1, p2), perm_compose(p1, p2))
[1, 2, 5, 3, 0, 4]

sage: p1 = [-1, 4, -1, -1, 1, 5, 8, -1, 6]
sage: p2 = [-1, 8, -1, -1, 4, 6, 5, -1, 1]
sage: perm_commutator(p1, p2)
[-1, 8, -1, -1, 5, 1, 4, -1, 6]
sage: perm_compose(perm_compose_i(p1, p2), perm_compose(p1, p2))
[-1, 8, -1, -1, 5, 1, 4, -1, 6]

surface_dynamics.misc.permutation.perm_compose(p1, p2, n=None)

Returns the product p1 p2.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_init, perm_compose
sage: perm_compose([0,2,1], [0,2,1])
[0, 1, 2]
sage: perm_compose([-1,2,3,1], [-1,2,1,3])
[-1, 1, 3, 2]

sage: p1 = perm_init('(1,3,5)', partial=True)
sage: p2 = perm_init('(1,5)(3)', partial=True)
sage: perm_compose(p1, p2)
[-1, 3, -1, 1, -1, 5]

surface_dynamics.misc.permutation.perm_compose_i(p1, p2, n=None)

Returns the product p1^{-1} p2^{-1}.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_compose_i
sage: perm_compose_i([0,1,2],[1,2,0])
[2, 0, 1]

sage: from surface_dynamics.misc.permutation import perm_invert, perm_compose
sage: from itertools import permutations
sage: for p1 in permutations(range(4)):
....:     for p2 in permutations(range(4)):
....:         assert perm_compose_i(p1, p2) == perm_compose(perm_invert(p1), perm_invert(p2))

surface_dynamics.misc.permutation.perm_conjugate(p1, p2, n=None)

Conjugate p1 by p2.

Let call res the output of this function. If p1 was mapping a to b then res will map p2[a] to p2[b].

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_random, perm_conjugate

sage: p1 = perm_random(23)
sage: p2 = perm_random(23)
sage: res = perm_conjugate(p1, p2)
sage: res[p2[14]] == p2[p1[14]]
True
sage: res[p2[19]] == p2[p1[19]]
True

surface_dynamics.misc.permutation.perm_conjugate_inplace(p1, p2, n=None)

Conjugation inplace.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_conjugate, perm_conjugate_inplace
sage: p1 = [2, 0, 3, 5, 1, 7, 4, 6]
sage: p2 = [6, 1, 0, 4, 2, 3, 5, 7]
sage: perm_conjugate(p1, p2)
[4, 6, 1, 7, 3, 2, 0, 5]
sage: perm_conjugate_inplace(p1, p2)
sage: print(p1)
[4, 6, 1, 7, 3, 2, 0, 5]

surface_dynamics.misc.permutation.perm_cycle_string(p, singletons=False, n=None)

Returns a string representing the cycle decomposition of p

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_cycle_string
sage: perm_cycle_string([0,2,1])
'(1,2)'
sage: perm_cycle_string([0,2,1], True)
'(0)(1,2)'
sage: perm_cycle_string([0,1,2,-1], False, 3)
'()'

surface_dynamics.misc.permutation.perm_cycle_type(p, n=None)

Return the lengths of the cycles of the permutation p in size of decreasing order.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_cycle_type
sage: perm_cycle_type([1,2,3,0])
[4]
sage: perm_cycle_type([0,2,3,1])
[3, 1]
sage: perm_cycle_type([3,2,1,0])
[2, 2]
sage: perm_cycle_type([3,1,2,0])
[2, 1, 1]
sage: perm_cycle_type([0,1,2,3])
[1, 1, 1, 1]
sage: perm_cycle_type([-1,4,2,-1,1])
[2, 1]

surface_dynamics.misc.permutation.perm_cycles(p, singletons=False, n=None)

Return the cycle decomposition of p

INPUT:

• p – the permutation

• singletons – bool (default: False) - return or not the singletons

• n - (optional) only use the first n elements of the permutation p

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_cycles, perm_init
sage: perm_cycles([0,2,1])
[[1, 2]]
sage: perm_cycles([0,2,1],True)
[[0], [1, 2]]

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

sage: perm_cycles([2,0,1,-1,-1], n=3)
[[0, 2, 1]]

sage: perm_cycles([-1,3,-1,1], singletons=True)
[[1, 3]]

sage: perm_cycles(perm_init('(1,3)', partial=True))
[[1, 3]]

sage: perm_cycles([-1, 7, -1, 5, -1, 3, -1, 1, -1, -1, -1, -1])
[[1, 7], [3, 5]]

surface_dynamics.misc.permutation.perm_dense_cycles(p, n=None)

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_dense_cycles

sage: perm_dense_cycles([1,2,0])
([0, 0, 0], [3])

sage: perm_dense_cycles([0,2,1])
([0, 1, 1], [1, 2])

sage: perm_dense_cycles([2,1,0])
([0, 1, 0], [2, 1])

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

surface_dynamics.misc.permutation.perm_dense_cycles_and_angles(p, n=None)

surface_dynamics.misc.permutation.perm_from_base64_str(s, n)

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_from_base64_str, perm_base64_str
sage: from array import array

sage: p = [3,0,2,1]
sage: s = perm_base64_str(p)
sage: perm_from_base64_str(s, 4) == p
True

sage: perm_base64_str([-1,-1])
'..'
sage: perm_from_base64_str('..', 2)
[-1, -1]

sage: p = list(range(3000))
sage: shuffle(p)
sage: perm_from_base64_str(perm_base64_str(p), 3000) == p
True
sage: p[18] = p[2003] = -1
sage: perm_from_base64_str(perm_base64_str(p), 3000) == p
True

surface_dynamics.misc.permutation.perm_hash(p, n=None)

Return a hash of the permutation p.

surface_dynamics.misc.permutation.perm_init(data, n=None, partial=False)

Returns a permutation from data.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_init
sage: perm_init([3,2,1,0])
[3, 2, 1, 0]
sage: perm_init([3,2,1,0], 5)
[3, 2, 1, 0, 4]
sage: perm_init(([2,1],[3,4,0]))
[3, 2, 1, 4, 0]
sage: perm_init('(0,1)(3,2)')
[1, 0, 3, 2]
sage: perm_init([3,1,-1,0])
[3, 1, -1, 0]
sage: perm_init([[2,1],[3,4,0]])
[3, 2, 1, 4, 0]

sage: perm_init([0r])
[0]

Zerology:

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

surface_dynamics.misc.permutation.perm_invert(l, n=None)

Returns the inverse of the permutation l.

TESTS:

sage: from itertools import permutations
sage: from surface_dynamics.misc.permutation import perm_init, perm_invert, perm_compose, perm_is_one
sage: all(perm_is_one(perm_compose(perm_invert(p),p)) for p in permutations(range(3)))
True
sage: all(perm_is_one(perm_compose(p,perm_invert(p))) for p in permutations(range(3)))
True

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

sage: p = perm_init('(1,3,5)(2,9)', partial=True)
sage: q = perm_invert(p)
sage: q
[-1, 5, 9, 1, -1, 3, -1, -1, -1, 2]
sage: perm_is_one(perm_compose(p, q))
True

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

surface_dynamics.misc.permutation.perm_invert_inplace(p, n=None)

Inverse in place the permutation p

surface_dynamics.misc.permutation.perm_is_on_list_stabilizer(p, a, n=None, eq=None)

Return whether the permutation p stabilizes the array a.

surface_dynamics.misc.permutation.perm_is_one(l, n=None)

Test whether l is the identity on its domain.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_is_one
sage: perm_is_one([])
True
sage: perm_is_one([-1])
True
sage: perm_is_one([0])
True
sage: perm_is_one([1, 0])
False

sage: perm_is_one([0, -1])
True
sage: perm_is_one([-1, 1])
True

sage: perm_is_one([0, 2, 1], 1)
True

surface_dynamics.misc.permutation.perm_is_regular(p, k=None, n=None)

Return whether the cycle decomposition of p is only made of cycles of identical lengths.

INPUT:

• p – permutation

• k – optional integer

• n – optional integer

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_is_regular
sage: perm_is_regular([1, 2, 0], 3)
True
sage: perm_is_regular([1, 2, 0])
True
sage: perm_is_regular([1, 2, 0, -1, 5, 6, 4], 3)
True
sage: perm_is_regular([1, 2, 0, -1, 5, 6, 4])
True
sage: perm_is_regular([], 3)
True
sage: perm_is_regular([])
True
sage: perm_is_regular([-1, -1], 5)
True
sage: perm_is_regular([-1, -1])
True

sage: from surface_dynamics.misc.permutation import perm_cycle_type
sage: import itertools
sage: for p in itertools.permutations(range(6)):
....:     assert perm_is_regular(p, 1) == (perm_cycle_type(p) == [1] * 6)
....:     assert perm_is_regular(p, 2) == (perm_cycle_type(p) == [2] * 3)
....:     assert perm_is_regular(p, 3) == (perm_cycle_type(p) == [3] * 2)
....:     assert perm_is_regular(p, 6) == (perm_cycle_type(p) == [6] * 1)
....:     assert perm_is_regular(p) == (perm_cycle_type(p) in [[1] * 6, [2] * 3, [3] * 2, [6] * 1])

surface_dynamics.misc.permutation.perm_num_cycles(p, n=None)

Return the number of cycles of the permutation p.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_num_cycles
sage: perm_num_cycles([1,2,3,0])
1
sage: perm_num_cycles([0,2,3,1])
2
sage: perm_num_cycles([3,2,1,0])
2
sage: perm_num_cycles([3,1,2,0])
3
sage: perm_num_cycles([0,1,2,3])
4
sage: perm_num_cycles([-1,4,2,-1,1])
2

surface_dynamics.misc.permutation.perm_on_cyclic_list(p, t)

Action of the permutation p on the list t up to cyclic order.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_on_cyclic_list
sage: perm_on_cyclic_list([0,1,2], [2,1,2])
[1, 2, 2]
sage: perm_on_cyclic_list([0,1], [0,1,0,0,1,0,0,0,1,1])
[0, 0, 0, 1, 1, 0, 1, 0, 0, 1]

sage: a = [1, 0, 3, 2, 5, 4]
sage: perm_on_cyclic_list(a, [0, 5, 3])
[1, 4, 2]
sage: perm_on_cyclic_list(a, [1, 4, 2])
[0, 5, 3]

sage: a1 = [0, 1, 4, 2, 3, 5]
sage: a2 = [1, 5, 3, 4, 2, 0]
sage: a3 = [2, 3, 1, 5, 0, 4]
sage: a4 = [5, 0, 2, 3, 4, 1]
sage: t1 = [0, 5, 1]
sage: t2 = [2, 4, 3]
sage: perm_on_cyclic_list(a1, t1) == perm_on_cyclic_list(a2, t1) == perm_on_cyclic_list(a4, t1) == t1
True
sage: perm_on_cyclic_list(a3, t1) == t2
True
sage: perm_on_cyclic_list(a3, t2) == t1
True

surface_dynamics.misc.permutation.perm_on_list(p, t)

Action of the permutation p on the list t.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_on_list
sage: perm_on_list([2,1,3,0], [2,1,2,0])
[3, 1, 3, 2]

surface_dynamics.misc.permutation.perm_on_list_inplace(p, a, n=None, swap=None)

Inplace action of permutation on list-like objects.

INPUT:

• p - permutation

• a - list, array

• n - (optional) size of permutation

• swap - (optional) a swap function

EXAMPLES:

sage: from surface_dynamics.misc.permutation import *
sage: l = [0,1,2,3,4]
sage: p = [4,2,3,0,1]
sage: perm_on_list_inplace(p,l)
sage: l
[3, 4, 1, 2, 0]

Permutation action on matrix rows:

sage: m1 = matrix(ZZ, 5, 5, 1)
sage: m2 = matrix(ZZ, 5, 5, 1)
sage: m = matrix(ZZ, 5, 5, 1)
sage: p1 = perm_init([4,1,3,2,0])
sage: p2 = perm_init([1,0,3,4,2])
sage: perm_on_list_inplace(p1, m1, swap=sage.matrix.matrix0.Matrix.swap_rows)
sage: perm_on_list_inplace(p2, m2, swap=sage.matrix.matrix0.Matrix.swap_rows)
sage: perm_on_list_inplace(perm_compose(p1, p2), m, swap=sage.matrix.matrix0.Matrix.swap_rows)
sage: m == m2 * m1
True

surface_dynamics.misc.permutation.perm_one(n)

The identity permutation

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_one
sage: perm_one(0)
[]
sage: perm_one(3)
[0, 1, 2]

surface_dynamics.misc.permutation.perm_orbit(p, i)

Returns the orbit of an integer i under the permutation p

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_orbit
sage: perm_orbit([0,3,1,2],2)
[2, 1, 3]

surface_dynamics.misc.permutation.perm_order(p, n=None)

Return the multiplicative order of the permutation p.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_init, perm_order
sage: p = perm_init('(1,3)(2,4,6)(5)')
sage: perm_order(p)
6

surface_dynamics.misc.permutation.perm_random(n)

Return a random permutation.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_random, perm_check
sage: perm_check(perm_random(13), 13)
True

surface_dynamics.misc.permutation.perm_random_centralizer(p)

Return a random permutation in the centralizer of p.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_random, perm_compose, perm_random_centralizer
sage: p = perm_random(10)
sage: q = perm_random_centralizer(p)
sage: perm_compose(p, q) == perm_compose(q, p)
True

surface_dynamics.misc.permutation.perm_random_conjugacy_class(c)

Return a random permutation with given conjugacy class c.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import (perm_random_conjugacy_class,
....:     perm_cycle_type)

sage: p = perm_random_conjugacy_class([5,2])
sage: perm_cycle_type(p)
[5, 2]

sage: p = perm_random_conjugacy_class([7,3,3,1])
sage: perm_cycle_type(p)
[7, 3, 3, 1]

surface_dynamics.misc.permutation.perm_switch(p1, p2, i, j)

Exchanges the values at positions i and j in two permutations p_1 and p_2.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_switch
sage: a = [0,1,2]
sage: b = [1,2,0]
sage: perm_switch(a,b,0,1)
sage: a;b
[1, 0, 2]
[2, 1, 0]

surface_dynamics.misc.permutation.perm_to_permutation(l)

Returns a permutation on [1, n] from a list on [0, n-1]

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perm_to_permutation
sage: perm_to_permutation([2,1,0])
(1,3)

surface_dynamics.misc.permutation.perms_are_transitive(p, n=None)

Test whether the group generated by the permutations in p is transitive.

INPUT:

• p - a list of permutations of [0, n-1]

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perms_are_transitive
sage: perms_are_transitive([[0,1,2],[0,2,1]])
False
sage: perms_are_transitive([[0,1,2],[1,2,0]])
True

sage: p0 = [0,2,3,1,7,5,6,4]
sage: p1 = [7,1,2,3,4,5,6,0]
sage: p2 = [6,1,2,3,4,5,0,7]
sage: p3 = [1,0,2,3,4,5,6,7]
sage: p4 = [0,1,4,5,2,3,6,7]
sage: perms_are_transitive([p0,p1,p2,p3,p4])
True
sage: perms_are_transitive([p0,p1,p2,p3])
False

surface_dynamics.misc.permutation.perms_canonical_labels(p, e=None)

surface_dynamics.misc.permutation.perms_canonical_labels_from(x, y, j0)

Return canonical labels for x, y that starts at j0.

INPUT:

• x – list - a permutation of [0, …, n] as a list

• y – list of permutations of [0, …, n] as a list of lists

• j0 – an index in [0, …, n]

OUTPUT:

mapping: a permutation that specify the new labels

EXAMPLES:

sage: from surface_dynamics.misc.constellation import perms_canonical_labels_from
sage: perms_canonical_labels_from([0,1,2],[[1,2,0]],0)
[0, 1, 2]
sage: perms_canonical_labels_from([1,0,2],[[2,0,1]],0)
[0, 1, 2]
sage: perms_canonical_labels_from([1,0,2],[[2,0,1]],1)
[1, 0, 2]
sage: perms_canonical_labels_from([1,0,2],[[2,0,1]],2)
[2, 1, 0]

surface_dynamics.misc.permutation.perms_orbits(p, n=None)

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perms_orbits

sage: p0 = [0,2,3,1,7,5,6,4]
sage: p1 = [7,1,2,3,4,5,6,0]
sage: p2 = [6,1,2,3,4,5,0,7]
sage: p3 = [1,0,2,3,4,5,6,7]

sage: perms_orbits([p0])
[[0], [1, 2, 3], [4, 7], [5], [6]]
sage: perms_orbits([p0, p1])
[[0, 7, 4], [1, 2, 3], [5], [6]]
sage: perms_orbits([p0, p1, p2, p3])
[[0, 7, 6, 1, 2, 3, 4], [5]]

surface_dynamics.misc.permutation.perms_relabel(p, m)

Relabel the list of permutations p according to m.

INPUT:

• p - a list of permutations

• m - the relabeling permutation

EXAMPLES:

sage: from surface_dynamics.misc.constellation import perms_relabel
sage: perms_relabel([[0,1,2],[0,2,1]],[2,1,0])
[[0, 1, 2], [1, 0, 2]]

surface_dynamics.misc.permutation.perms_transitive_components(p, n=None)

Return the list of transitive components of the subgroup generated by the permutations p.

INPUT:

• p – a list of permutations given as lists

EXAMPLES:

sage: from surface_dynamics.misc.permutation import perms_transitive_components

sage: perms_transitive_components([[1,0,2,3],[0,1,3,2]])
[(0, 1), (2, 3)]

sage: perms_transitive_components([[2,3,0,1]])
[(0, 2), (1, 3)]

sage: perms_transitive_components([[3,1,2,0], [0,3,2,1], [0,1,3,2]])
[(0, 1, 2, 3)]

surface_dynamics.misc.permutation.permutation_to_perm(p)

Return a list on [0, n-1] from a permutation on [1, n]

EXAMPLES:

sage: from surface_dynamics.misc.permutation import permutation_to_perm
sage: permutation_to_perm(PermutationGroupElement([3,1,2]))
[2, 0, 1]

surface_dynamics.misc.permutation.str_to_cycles(s)

Returns a list of cycles from a string.

EXAMPLES:

sage: from surface_dynamics.misc.permutation import str_to_cycles
sage: str_to_cycles('(0,1)')
[[0, 1]]
sage: str_to_cycles('(0,1)(3,2)')
[[0, 1], [3, 2]]

sage: str_to_cycles('()(0,1)()(2,3)')
[[0, 1], [2, 3]]

surface_dynamics.misc.permutation.uint_base64_str(n, l=None)

EXAMPLES:

sage: from surface_dynamics.misc.permutation import uint_base64_str

sage: uint_base64_str(15)
'f'
sage: uint_base64_str(15, 3)
'00f'

sage: uint_base64_str(-1)
'.'
sage: uint_base64_str(-1, 3)
'...'

surface_dynamics.misc.permutation.uint_from_base64_str(s)

EXAMPLES:

sage: from surface_dynamics.misc.permutation import uint_from_base64_str, uint_base64_str

sage: uint_from_base64_str('mqb')
91787
sage: uint_base64_str(91787)
'mqb'

sage: uint_from_base64_str('00mqb')
91787

sage: uint_from_base64_str('...')
-1