Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
r""" Constellations
A constellation is a tuple `(g_0, g_1, \dots, g_k)` of permutations such that the product `g_0 g_1 ... g_k` is the identity. One often assumes that the group generated by `g_0, g_1, \dots, g_k` acts transitively ([LaZv04]_ definition 1). Geometrically, it corresponds to a covering of the 2-sphere ramified over `k` points (the transitivity condition corresponds to the connectivity of the covering).
EXAMPLES::
sage: c = Constellation(['(1,2)', '(1,3)', None]) sage: c Constellation of length 3 and degree 3 g0 (1,2)(3) g1 (1,3)(2) g2 (1,3,2) sage: C = Constellations(3,4); C Connected constellations of length 3 and degree 4 on {1, 2, 3, 4} sage: C.cardinality() 426
sage: C = Constellations(3, 4, domain=('a', 'b', 'c', 'd')) sage: C Connected constellations of length 3 and degree 4 on {'a', 'b', 'c', 'd'} sage: c = C(('a','c'),(('b','c'),('a','d')), None) sage: c Constellation of length 3 and degree 4 g0 ('a','c')('b')('d') g1 ('a','d')('b','c') g2 ('a','d','c','b') sage: c.is_connected() True sage: c.euler_characteristic() 2 sage: TestSuite(C).run()
REFERENCES:
.. [LaZv04] S. Lando and A. Zvonkine, "Graphs on surfaces and their applications", Springer-Verlag, 2004. """
#***************************************************************************** # Copyright (C) 2015-2016 Vincent Delecroix <20100.delecroix@gmail.com> # Frederic Chapoton <fchapoton2@gmail.com> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
rich_to_bool)
# constructors
r""" Build a set of constellations.
INPUT:
- ``profile`` -- an optional profile
- ``length`` -- an optional length
- ``degree`` -- an optional degree
- ``connected`` -- an optional boolean
EXAMPLES::
sage: Constellations(4,2) Connected constellations of length 4 and degree 2 on {1, 2}
sage: Constellations([[3,2,1],[3,3],[3,3]]) Connected constellations with profile ([3, 2, 1], [3, 3], [3, 3]) on {1, 2, 3, 4, 5, 6} """
else: length = Integer(data[0])
else: raise ValueError("the size of the domain should be equal to the degree")
sym, bool(connected)) else: raise ValueError("you must either provide a profile or a pair (length, degree)")
r""" Constellation
INPUT:
- ``g`` -- a list of permutations
- ``mutable`` -- whether the result is mutable or not. Default is ``False``.
- ``connected`` -- whether the result should be connected. Default is ``True``.
- ``check`` -- whether or not to check. If it is ``True``, then the list ``g`` must contains no ``None``.
EXAMPLES:
Simple initialization::
sage: Constellation(['(0,1)','(0,3)(1,2)','(0,3,1,2)']) Constellation of length 3 and degree 4 g0 (0,1)(2)(3) g1 (0,3)(1,2) g2 (0,3,1,2)
One of the permutation can be omitted::
sage: Constellation(['(0,1)', None, '(0,4)(1,2,3)']) Constellation of length 3 and degree 5 g0 (0,1)(2)(3)(4) g1 (0,3,2,1,4) g2 (0,4)(1,2,3)
One can define mutable constellations::
sage: Constellation(([0,2,1], [2,1,0], [1,2,0]), mutable=True) Constellation of length 3 and degree 3 g0 (0)(1,2) g1 (0,2)(1) g2 (0,1,2) """ domain=sym.domain(), connected=connected)(g, mutable=mutable, check=check)
# classes
r""" Constellation
A constellation or a tuple of permutations `(g_0,g_1,...,g_k)` such that the product `g_0 g_1 ... g_k` is the identity. """ r""" TESTS::
sage: c = Constellation([[1,2,0],[0,2,1],[1,0,2],None]) sage: c == loads(dumps(c)) True sage: g0 = '(0,1)(2,4)' sage: g1 = '(0,3)(1,4)' sage: g2 = '(2,4,3)' sage: g3 = '(0,3)(1,2)' sage: c0 = Constellation([g0,g1,g2,g3]) sage: c0 == Constellation([None,g1,g2,g3]) True sage: c0 == Constellation([g0,None,g2,g3]) True sage: c0 == Constellation([g0,g1,None,g3]) True sage: c0 == Constellation([g0,g1,g2,None]) True """
r""" Return a hash for ``self``.
EXAMPLES::
sage: c = Constellation(([0,2,1],[2,1,0],[1,2,0]), mutable=False) sage: c.__hash__() 5481133608926415725 # 64-bit 511937389 # 32-bit """ raise ValueError("can not hash mutable constellation")
r""" Do nothing, as ``self`` is already immutable.
EXAMPLES::
sage: c = Constellation(([0,2,1],[2,1,0],[1,2,0]), mutable=False) sage: c.set_immutable() sage: c.is_mutable() False """
r""" Return ``False`` as ``self`` is immutable.
EXAMPLES::
sage: c = Constellation(([0,2,1],[2,1,0],[1,2,0]), mutable=False) sage: c.is_mutable() False """
r""" Perform the multiplication by the transposition `(j0, j1)` between the permutations `g_i` and `g_{i+1}`.
The modification is local in the sense that it modifies `g_i` and `g_{i+1}` but does not modify the product `g_i g_{i+1}`. The new constellation is
.. MATH::
(g_0, \ldots, g_{i-1}, g_{i} (j0 j1), (j0 j1) g_{i+1}, g_{i+2}, \ldots, g_k)
EXAMPLES::
sage: c = Constellation(['(0,1)(2,3,4)','(1,4)',None], mutable=True); c Constellation of length 3 and degree 5 g0 (0,1)(2,3,4) g1 (0)(1,4)(2)(3) g2 (0,1,3,2,4) sage: c.is_mutable() True sage: c.switch(1,2,3); c Constellation of length 3 and degree 5 g0 (0,1)(2,3,4) g1 (0)(1,4)(2,3) g2 (0,1,3,4)(2) sage: c._check() sage: c.switch(2,1,3); c Constellation of length 3 and degree 5 g0 (0,1,4,2,3) g1 (0)(1,4)(2,3) g2 (0,3,4)(1)(2) sage: c._check() sage: c.switch(0,0,1); c Constellation of length 3 and degree 5 g0 (0)(1,4,2,3) g1 (0,4,1)(2,3) g2 (0,3,4)(1)(2) sage: c._check() """ raise ValueError("this constellation is immutable." " Take a mutable copy first.") raise ValueError("index out of range")
r""" Return the Euler characteristic of the surface.
ALGORITHM:
Hurwitz formula
EXAMPLES::
sage: c = Constellation(['(0,1)', '(0,2)', None]) sage: c.euler_characteristic() 2
sage: c = Constellation(['(0,1,2,3)','(1,3,0,2)', '(0,3,1,2)', None]) sage: c.euler_characteristic() -4
TESTS::
sage: parent(c.euler_characteristic()) Integer Ring """ sum(sum(j - 1 for j in self.profile(i)) for i in range(self.length())))
r""" Return the genus of the surface.
EXAMPLES::
sage: c = Constellation(['(0,1)', '(0,2)', None]) sage: c.genus() 0
sage: c = Constellation(['(0,1)(2,3,4)','(1,3,4)(2,0)', None]) sage: c.genus() 1
TESTS::
sage: parent(c.genus()) Integer Ring """
r""" Check that the constellation is valid and if not raise ValueError.
TESTS::
sage: c = Constellation([[0,1],[1,0]], mutable=True, check=False) sage: c._check() Traceback (most recent call last): ... ValueError: the product is not identity
sage: c = Constellation([[0,1],[0,1]], mutable=True, check=False) sage: c._check() Traceback (most recent call last): ... ValueError: not connected """
r""" Return a copy of ``self``.
TESTS::
sage: c = Constellation([[0,2,1],[1,0,2],[2,1,0],None]) sage: c == copy(c) True sage: c is copy(c) False sage: c = Constellation([[0,2,1],[1,0,2],[2,1,0],None],mutable=True) sage: c == copy(c) True sage: c is copy(c) False """ check=False, mutable=self._mutable)
r""" Return a mutable copy of ``self``.
EXAMPLES::
sage: c = Constellation(([0,2,1],[2,1,0],[1,2,0]), mutable=False) sage: d = c.mutable_copy() sage: d.is_mutable() True """ check=False, mutable=True)
# GENERAL PROPERTIES
r""" Test of connectedness.
EXAMPLES::
sage: c = Constellation(['(0,1)(2)', None, '(0,1)(2)'], connected=False) sage: c.is_connected() False sage: c = Constellation(['(0,1,2)', None], connected=False) sage: c.is_connected() True """ else:
""" Return the connected components.
OUTPUT:
A list of connected constellations.
EXAMPLES::
sage: c = Constellation(['(0,1)(2)', None, '(0,1)(2)'], connected=False) sage: cc = c.connected_components(); cc [Constellation of length 3 and degree 2 g0 (0,1) g1 (0)(1) g2 (0,1), Constellation of length 3 and degree 1 g0 (0) g1 (0) g2 (0)] sage: all(c2.is_connected() for c2 in cc) True
sage: c = Constellation(['(0,1,2)', None], connected=False) sage: c.connected_components() [Constellation of length 2 and degree 3 g0 (0,1,2) g1 (0,2,1)] """ return [self]
r""" Do the comparison.
TESTS::
sage: Constellation(['(0,1,2)', None]) == Constellation(['(0,1,2)', None]) True sage: Constellation(['(0,1)','(0,2)',None]) == Constellation(['(0,1)',None,'(0,2)']) False
sage: Constellation(['(0,1,2)', None]) != Constellation(['(0,1,2)', None]) False sage: Constellation(['(0,1)','(0,2)',None]) != Constellation(['(0,1)',None,'(0,2)']) True
sage: c1 = Constellation([[1,2,0],None]) sage: c2 = Constellation([[2,0,1],None]) sage: c1 < c2 True sage: c2 > c1 True """ return op == op_NE
return richcmp_not_equal(lx, rx, op)
return richcmp_not_equal(lx, rx, op)
return rich_to_bool(op, 0)
r""" Test of isomorphism.
Return ``True`` if the constellations are isomorphic (*i.e.* related by a common conjugacy) and return the permutation that conjugate the two permutations if ``return_map`` is ``True`` in such a way that ``self.relabel(m) == other``.
ALGORITHM:
uses canonical labels obtained from the method :meth:`relabel`.
EXAMPLES::
sage: c = Constellation([[1,0,2],[2,1,0],[0,2,1],None]) sage: d = Constellation([[2,1,0],[0,2,1],[1,0,2],None]) sage: answer, mapping = c.is_isomorphic(d,return_map=True) sage: print(answer) True sage: c.relabel(mapping) == d True """ self.length() == other.length()): return False, None return False, None
self.length() == other.length() and self.relabel() == other.relabel())
r""" Return a string representation.
EXAMPLES::
sage: c = Constellation([[1,0,2],[2,1,0],[0,2,1],None]) sage: c._repr_() 'Constellation of length 4 and degree 3\ng0 (0,1)(2)\ng1 (0,2)(1)\ng2 (0)(1,2)\ng3 (0,2)(1)' """ self.degree())
r""" Return the degree of the constellation.
The degree of a constellation is the number `n` that corresponds to the symmetric group `S(n)` in which the permutations of the constellation are defined.
EXAMPLES::
sage: c = Constellation([]) sage: c.degree() 0 sage: c = Constellation(['(0,1)',None]) sage: c.degree() 2 sage: c = Constellation(['(0,1)','(0,3,2)(1,5)',None,'(4,3,2,1)']) sage: c.degree() 6
TESTS::
sage: parent(c.degree()) Integer Ring """
r""" Return the number of permutations.
EXAMPLES::
sage: c = Constellation(['(0,1)','(0,2)','(0,3)',None]) sage: c.length() 4 sage: c = Constellation(['(0,1,3)',None,'(1,2)']) sage: c.length() 3
TESTS::
sage: parent(c.length()) Integer Ring """
r""" Return the profile of ``self``.
The profile of a constellation is the tuple of partitions associated to the conjugacy classes of the permutations of the constellation.
This is also called the passport.
EXAMPLES::
sage: c = Constellation(['(0,1,2)(3,4)','(0,3)',None]) sage: c.profile() ([3, 2], [2, 1, 1, 1], [5]) """ else:
# ACCESS TO INDIVIDUAL PERMUTATION
r""" Return the permutation `g_i` of the constellation.
INPUT:
- i -- integer or ``None`` (default)
If ``None`` , return instead the list of all `g_i`.
EXAMPLES::
sage: c = Constellation(['(0,1,2)(3,4)','(0,3)',None]) sage: c.g(0) (0,1,2)(3,4) sage: c.g(1) (0,3) sage: c.g(2) (0,4,3,2,1) sage: c.g() [(0,1,2)(3,4), (0,3), (0,4,3,2,1)] """ else:
r""" Relabel ``self``.
If ``perm`` is provided then relabel with respect to ``perm``. Otherwise use canonical labels. In that case, if ``return_map`` is provided, the return also the map used for canonical labels.
Algorithm:
the cycle for g(0) are adjacent and the cycle are joined with respect to the other permutations. The minimum is taken for all possible renumerotations.
EXAMPLES::
sage: c = Constellation(['(0,1)(2,3,4)','(1,4)',None]); c Constellation of length 3 and degree 5 g0 (0,1)(2,3,4) g1 (0)(1,4)(2)(3) g2 (0,1,3,2,4) sage: c2 = c.relabel(); c2 Constellation of length 3 and degree 5 g0 (0,1)(2,3,4) g1 (0)(1,2)(3)(4) g2 (0,1,4,3,2)
The map returned when the option ``return_map`` is set to ``True`` can be used to set the relabelling::
sage: c3, perm = c.relabel(return_map=True) sage: c3 == c2 and c3 == c.relabel(perm=perm) True
sage: S5 = SymmetricGroup(range(5)) sage: d = c.relabel(S5([4,3,1,0,2])); d Constellation of length 3 and degree 5 g0 (0,2,1)(3,4) g1 (0)(1)(2,3)(4) g2 (0,1,2,4,3) sage: d.is_isomorphic(c) True
We check that after a random relabelling the new constellation is isomorphic to the initial one::
sage: c = Constellation(['(0,1)(2,3,4)','(1,4)',None]) sage: p = S5.random_element() sage: cc = c.relabel(perm=p) sage: cc.is_isomorphic(c) True
Check that it works for "non standard" labels::
sage: c = Constellation([(('a','b'),('c','d','e')),('b','d'), None]) sage: c.relabel() Constellation of length 3 and degree 5 g0 ('a','b')('c','d','e') g1 ('a')('b','c')('d')('e') g2 ('a','b','e','d','c') """
else:
# compute canonical labels raise ValueError("No canonical labels implemented for" " non connected constellation")
# get the permutations on {0, 1, ..., d-1} # compute the canonical labels # map it back to the domain # TODO: a lot of time is lost here!
else:
# BRAID GROUP ACTION
r""" Act on ``self`` as the braid group generator that exchanges position `i` and `i+1`.
INPUT:
- ``i`` -- integer in `[0, n-1]` where `n` is the length of ``self``
EXAMPLES::
sage: sigma = lambda c, i: c.braid_group_action(i)
sage: c = Constellation(['(0,1)(2,3,4)','(1,4)',None]); c Constellation of length 3 and degree 5 g0 (0,1)(2,3,4) g1 (0)(1,4)(2)(3) g2 (0,1,3,2,4) sage: sigma(c, 1) Constellation of length 3 and degree 5 g0 (0,1)(2,3,4) g1 (0,1,3,2,4) g2 (0,3)(1)(2)(4)
Check the commutation relation::
sage: c = Constellation(['(0,1)(2,3,4)','(1,4)','(2,5)(0,4)',None]) sage: d = Constellation(['(0,1,3,5)','(2,3,4)','(0,3,5)',None]) sage: c13 = sigma(sigma(c, 0), 2) sage: c31 = sigma(sigma(c, 2), 0) sage: c13 == c31 True sage: d13 = sigma(sigma(d, 0), 2) sage: d31 = sigma(sigma(d, 2), 0) sage: d13 == d31 True
Check the braid relation::
sage: c121 = sigma(sigma(sigma(c, 1), 2), 1) sage: c212 = sigma(sigma(sigma(c, 2), 1), 2) sage: c121 == c212 True sage: d121 = sigma(sigma(sigma(d, 1), 2), 1) sage: d212 = sigma(sigma(sigma(d, 2), 1), 2) sage: d121 == d212 True """ txt = "i should be between 0 and {}" raise ValueError(txt.format(self.length() - 1))
r""" Return the graph of the action of the braid group.
The action is considered up to isomorphism of constellation.
EXAMPLES::
sage: c = Constellation(['(0,1)(2,3,4)','(1,4)',None]); c Constellation of length 3 and degree 5 g0 (0,1)(2,3,4) g1 (0)(1,4)(2)(3) g2 (0,1,3,2,4) sage: G = c.braid_group_orbit() sage: G.num_verts() 4 sage: G.num_edges() 12 """
r""" Constellations of given length and degree.
EXAMPLES::
sage: C = Constellations(2,3); C Connected constellations of length 2 and degree 3 on {1, 2, 3} sage: C([[2,3,1],[3,1,2]]) Constellation of length 2 and degree 3 g0 (1,2,3) g1 (1,3,2) sage: C.cardinality() 2 sage: Constellations(2,3,connected=False).cardinality() 6 """
""" TESTS::
sage: TestSuite(Constellations(length=6,degree=4)).run(skip='_test_cardinality') """ raise ValueError("length should be a non-negative integer") raise ValueError("degree should be a non-negative integer")
r""" Return whether this set of constellations is empty.
EXAMPLES::
sage: Constellations(2, 3).is_empty() False sage: Constellations(1, 2).is_empty() True sage: Constellations(1, 2, connected=False).is_empty() False """
r""" TESTS::
sage: C = Constellations(2, 3, connected=True) sage: D = Constellations(2, 3, connected=False) sage: e1 = [[3,1,2], None] sage: e2 = [[1,2,3], None] sage: C(e1) in C True sage: D(e1) in C True sage: D(e1) in D True sage: D(e2) in C False sage: D(e2) in D True
sage: e1 in C and e1 in D True sage: e2 in C False sage: e2 in D True """ else: return False (elt.length() == self._length and elt.degree() == self._degree and (not self._connected or elt.is_connected())))
""" TESTS::
sage: Constellations(3,3)._repr_() 'Connected constellations of length 3 and degree 3 on {1, 2, 3}' sage: Constellations(3,3,connected=False)._repr_() 'Constellations of length 3 and degree 3 on {1, 2, 3}' """ self._degree, self._sym.domain()) else:
""" Iterator over all constellations of given degree and length.
EXAMPLES::
sage: const = Constellations(3,3); const Connected constellations of length 3 and degree 3 on {1, 2, 3} sage: len([v for v in const]) 26
One can check the first few terms of sequence :oeis:`220754`::
sage: Constellations(4,1).cardinality() 1 sage: Constellations(4,2).cardinality() 7 sage: Constellations(4,3).cardinality() 194 sage: Constellations(4,4).cardinality() # long time 12858 """
if self._degree == 1: yield self([[0]]) return
r""" Return a random element.
This is found by trial and rejection, starting from a random list of permutations.
EXAMPLES::
sage: const = Constellations(3,3) sage: const.random_element() Constellation of length 3 and degree 3 ... ... ... sage: c = const.random_element() sage: c.degree() == 3 and c.length() == 3 True """
not G.is_transitive()):
r""" Build an element of ``self``.
EXAMPLES::
sage: C = Constellations(2,3) sage: C([[2,3,1],[3,1,2]]) Constellation of length 2 and degree 3 g0 (1,2,3) g1 (1,3,2) sage: C([[3,2,1],[3,2,1]]) Traceback (most recent call last): ... ValueError: not connected """ len(data[0]) == self._length: else:
else: raise ValueError("at most one permutation can be None")
raise ValueError("degree is not {}".format(self._degree)) raise ValueError("length is not {}".format(self._length)) else:
r""" Return a constellation in ``self``.
EXAMPLES::
sage: Constellations(2, 3).an_element() Constellation of length 2 and degree 3 g0 (1,3,2) g1 (1,2,3)
sage: Constellations(3, 5,domain='abcde').an_element() Constellation of length 3 and degree 5 g0 ('a','e','d','c','b') g1 ('a','b','c','d','e') g2 ('a')('b')('c')('d')('e')
sage: Constellations(0, 0).an_element() Constellation of length 0 and degree 0
sage: Constellations(1, 1).an_element() Constellation of length 1 and degree 1 g0 (1)
sage: Constellations(1, 2).an_element() Traceback (most recent call last): ... EmptySetError """
else: g = [domain[:]] * self._length
r""" Return a list of graphs that corresponds to the braid group action on ``self`` up to isomorphism.
OUTPUT:
- list of graphs
EXAMPLES::
sage: C = Constellations(3,3) sage: C.braid_group_action() [Looped multi-digraph on 3 vertices, Looped multi-digraph on 3 vertices, Looped multi-digraph on 1 vertex] """
r""" Return the orbits under the action of braid group.
EXAMPLES::
sage: C = Constellations(3,3) sage: O = C.braid_group_orbits() sage: len(O) 3 sage: [x.profile() for x in O[0]] [([1, 1, 1], [3], [3]), ([3], [1, 1, 1], [3]), ([3], [3], [1, 1, 1])] sage: [x.profile() for x in O[1]] [([2, 1], [2, 1], [3]), ([2, 1], [3], [2, 1]), ([3], [2, 1], [2, 1])] sage: [x.profile() for x in O[2]] [([3], [3], [3])] """
r""" Constellations with fixed profile.
EXAMPLES::
sage: C = Constellations([[3,1],[3,1],[2,2]]); C Connected constellations with profile ([3, 1], [3, 1], [2, 2]) on {1, 2, 3, 4} sage: C.cardinality() 24 sage: C.first() Constellation of length 3 and degree 4 g0 (1)(2,3,4) g1 (1,3,4)(2) g2 (1,3)(2,4) sage: C.last() Constellation of length 3 and degree 4 g0 (1,3,2)(4) g1 (1,4,2)(3) g2 (1,3)(2,4)
Note that the cardinality can also be computed using characters of the symmetric group (Frobenius formula)::
sage: P = Partitions(4) sage: p1 = Partition([3,1]) sage: p2 = Partition([3,1]) sage: p3 = Partition([2,2]) sage: i1 = P.cardinality() - P.rank(p1) - 1 sage: i2 = P.cardinality() - P.rank(p2) - 1 sage: i3 = P.cardinality() - P.rank(p3) - 1 sage: s = 0 sage: for c in SymmetricGroup(4).irreducible_characters(): ....: v = c.values() ....: s += v[i1] * v[i2] * v[i3] / v[0] sage: c1 = p1.conjugacy_class_size() sage: c2 = p2.conjugacy_class_size() sage: c3 = p3.conjugacy_class_size() sage: print(c1 * c2 * c3 / factorial(4)**2 * s) 1
The number obtained above is up to isomorphism. And we can check::
sage: len(C.isomorphism_representatives()) 1 """ r""" OPTIONS:
- ``profile`` -- a list of integer partitions of the same integer
- ``connected`` -- a boolean (default: ``True``) that specify if we consider only connected constellations.
TESTS::
sage: C = Constellations([(3,1),(3,1),(2,2)]) sage: TestSuite(C).run() """ raise ValueError("all partition in the passport should " "have the same sum.") else: raise ValueError("the size of the domain should be equal to the degree")
r""" TESTS::
sage: Constellations(profile=[[3,2,1],[3,3],[3,3]]) Connected constellations with profile ([3, 2, 1], [3, 3], [3, 3]) on {1, 2, 3, 4, 5, 6} """ self._cd._sym.domain()) return "Constellations " + s
r""" Return a set of isomorphism representative of ``self``.
EXAMPLES::
sage: C = Constellations([[5], [4,1], [3,2]]) sage: C.cardinality() 240 sage: ir = sorted(C.isomorphism_representatives()) sage: len(ir) 2 sage: ir[0] Constellation of length 3 and degree 5 g0 (1,2,3,4,5) g1 (1)(2,3,4,5) g2 (1,5,3)(2,4) sage: ir[1] Constellation of length 3 and degree 5 g0 (1,2,3,4,5) g1 (1)(2,5,3,4) g2 (1,5)(2,3,4) """
r""" Build an element of ``self``.
TESTS::
sage: C = Constellations([(3,1),(3,1),(2,2)]) sage: c = C([(2,3,4),(1,2,3),((1,2),(3,4))]); c Constellation of length 3 and degree 4 g0 (1)(2,3,4) g1 (1,2,3)(4) g2 (1,2)(3,4) sage: C([(1,2,3),(3,2,4),None]) Traceback (most recent call last): ... ValueError: wrong profile """
r""" Iterator of the elements in ``self``.
TESTS::
sage: C = Constellations([(3,1),(3,1),(2,2)]) sage: for c in C: print(c) Constellation of length 3 and degree 4 g0 (1)(2,3,4) g1 (1,3,4)(2) g2 (1,3)(2,4) Constellation of length 3 and degree 4 g0 (1)(2,3,4) g1 (1,4,2)(3) g2 (1,4)(2,3) ... Constellation of length 3 and degree 4 g0 (1,3,2)(4) g1 (1,3,4)(2) g2 (1,4)(2,3) Constellation of length 3 and degree 4 g0 (1,3,2)(4) g1 (1,4,2)(3) g2 (1,3)(2,4)
sage: C = Constellations([(3,1),(3,1),(2,2)], domain='abcd') sage: for c in C: print(c) Constellation of length 3 and degree 4 g0 ('a')('b','d','c') g1 ('a','b','d')('c') g2 ('a','b')('c','d') Constellation of length 3 and degree 4 g0 ('a')('b','d','c') g1 ('a','d','c')('b') g2 ('a','d')('b','c') ... Constellation of length 3 and degree 4 g0 ('a','b','c')('d') g1 ('a','b','d')('c') g2 ('a','d')('b','c') Constellation of length 3 and degree 4 g0 ('a','b','c')('d') g1 ('a','d','c')('b') g2 ('a','b')('c','d') """
if self._cd._degree == 1: yield self([[0]]) return
for pi in profile]):
# ************************************************************************* # auxiliary functions # *************************************************************************
r""" Return the domain of a single permutation (before initialization).
EXAMPLES::
sage: from sage.combinat.constellation import perm_sym_domain sage: perm_sym_domain([1,2,3,4]) {1, 2, 3, 4} sage: perm_sym_domain(((1,2),(0,4))) {0, 1, 2, 4} sage: perm_sym_domain('(1,2,0,5)') [1, 0, 2, 5] """ else: for a in cyc.split(',')]) else: return domain elif parent(g) in Groups: return g.domain() else: raise TypeError
r""" Initialize a list of permutations (in the same symmetric group).
OUTPUT:
- ``sym`` -- a symmetric group
- ``gg`` -- a list of permutations
EXAMPLES::
sage: from sage.combinat.constellation import perms_sym_init sage: S, g = perms_sym_init([[0,2,1,3], [1,3,2,0]]) sage: S.domain() {0, 1, 2, 3} sage: g [(1,2), (0,1,3)]
sage: S, g = perms_sym_init(['(2,1)', '(0,3)']) sage: S.domain() {0, 1, 2, 3} sage: g [(1,2), (0,3)]
sage: S, g = perms_sym_init([(1,0), (2,1)]) sage: S.domain() {0, 1, 2} sage: g [(0,1), (1,2)]
sage: S, g = perms_sym_init([((1,0),(2,3)), '(0,1,4)']) sage: S.domain() {0, 1, 2, 3, 4} sage: g [(0,1)(2,3), (0,1,4)] """
for s in domain): else:
except (ValueError, TypeError): return sym, None
""" Checks that the action of the generated group is transitive
INPUT:
- a list of permutations of `[0, n-1]` (in a SymmetricGroup)
- an integer `n`
EXAMPLES::
sage: from sage.combinat.constellation import perms_are_connected sage: S = SymmetricGroup(range(3)) sage: perms_are_connected([S([0,1,2]),S([0,2,1])],3) False sage: perms_are_connected([S([0,1,2]),S([1,2,0])],3) True """
r""" Return canonical labels for ``x``, ``y`` that starts at ``j0``
.. WARNING::
The group generated by ``x`` and the elements of ``y`` should be transitive.
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 sage.combinat.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] """
print("complete from {}".format(j0)) # initialize at j0 # complete x cycle from j0 print("completed cycle mapping = {}".format(mapping))
# find another guy print("try to find somebody in {}".format(waiting))
else: # found: complete cycle from new guy
""" Return the inverse of the permutation `p`.
INPUT:
a permutation of {0,..,n-1} given by a list of values
OUTPUT:
a permutation of {0,..,n-1} given by a list of values
EXAMPLES::
sage: from sage.combinat.constellation import perm_invert sage: perm_invert([3,2,0,1]) [2, 3, 1, 0] """
""" Return the conjugate of the permutation `p` by the permutation `s`.
INPUT:
two permutations of {0,..,n-1} given by lists of values
OUTPUT:
a permutation of {0,..,n-1} given by a list of values
EXAMPLES::
sage: from sage.combinat.constellation import perm_conjugate sage: perm_conjugate([3,1,2,0], [3,2,0,1]) [0, 3, 2, 1] """
""" Relabel a list with a common conjugation such that two conjugated lists are relabeled the same way.
INPUT:
- ``p`` is a list of at least 2 permutations
- ``e`` is None or a list of integer in the domain of the permutations. If provided, then the renumbering algorithm is only performed from the elements of ``e``.
OUTPUT:
- a pair made of a list of permutations (as a list of lists) and a list that corresponds to the conjugacy used.
EXAMPLES::
sage: from sage.combinat.constellation import perms_canonical_labels sage: l0 = [[2,0,3,1], [3,1,2,0], [0,2,1,3]] sage: l, m = perms_canonical_labels(l0); l [[1, 2, 3, 0], [0, 3, 2, 1], [2, 1, 0, 3]]
sage: S = SymmetricGroup(range(4)) sage: [~S(m) * S(u) * S(m) for u in l0] == list(map(S, l)) True
sage: perms_canonical_labels([]) Traceback (most recent call last): ... ValueError: input must have length >= 2 """
# get canonical label from i in to_test and compare
|