Disjoint union of enumerated sets

AUTHORS:

  • Florent Hivert (2009-07/09): initial implementation.

  • Florent Hivert (2010-03): classcall related stuff.

  • Florent Hivert (2010-12): fixed facade element construction.

class sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets(family, facade=True, keepkey=False, category=None)[source]

Bases: UniqueRepresentation, Parent

A class for disjoint unions of enumerated sets.

INPUT:

  • family – list (or iterable or family) of enumerated sets

  • keepkey – boolean

  • facade – boolean

This models the enumerated set obtained by concatenating together the specified ordered sets. The latter are supposed to be pairwise disjoint; otherwise, a multiset is created.

The argument family can be a list, a tuple, a dictionary, or a family. If it is not a family it is first converted into a family (see sage.sets.family.Family()).

Experimental options:

By default, there is no way to tell from which set of the union an element is generated. The option keepkey=True keeps track of those by returning pairs (key, el) where key is the index of the set to which el belongs. When this option is specified, the enumerated sets need not be disjoint anymore.

With the option facade=False the elements are wrapped in an object whose parent is the disjoint union itself. The wrapped object can then be recovered using the value attribute.

The two options can be combined.

The names of those options is imperfect, and subject to change in future versions. Feedback welcome.

EXAMPLES:

The input can be a list or a tuple of FiniteEnumeratedSets:

sage: U1 = DisjointUnionEnumeratedSets((
....:       FiniteEnumeratedSet([1,2,3]),
....:       FiniteEnumeratedSet([4,5,6])))
sage: U1
Disjoint union of Family ({1, 2, 3}, {4, 5, 6})
sage: U1.list()
[1, 2, 3, 4, 5, 6]
sage: U1.cardinality()
6

>>> from sage.all import *
>>> U1 = DisjointUnionEnumeratedSets((
...       FiniteEnumeratedSet([Integer(1),Integer(2),Integer(3)]),
...       FiniteEnumeratedSet([Integer(4),Integer(5),Integer(6)])))
>>> U1
Disjoint union of Family ({1, 2, 3}, {4, 5, 6})
>>> U1.list()
[1, 2, 3, 4, 5, 6]
>>> U1.cardinality()
6

The input can also be a dictionary:

sage: U2 = DisjointUnionEnumeratedSets({1: FiniteEnumeratedSet([1,2,3]),
....:                                   2: FiniteEnumeratedSet([4,5,6])})
sage: U2
Disjoint union of Finite family {1: {1, 2, 3}, 2: {4, 5, 6}}
sage: U2.list()
[1, 2, 3, 4, 5, 6]
sage: U2.cardinality()
6

>>> from sage.all import *
>>> U2 = DisjointUnionEnumeratedSets({Integer(1): FiniteEnumeratedSet([Integer(1),Integer(2),Integer(3)]),
...                                   Integer(2): FiniteEnumeratedSet([Integer(4),Integer(5),Integer(6)])})
>>> U2
Disjoint union of Finite family {1: {1, 2, 3}, 2: {4, 5, 6}}
>>> U2.list()
[1, 2, 3, 4, 5, 6]
>>> U2.cardinality()
6

However in that case the enumeration order is not specified.

In general the input can be any family:

sage: # needs sage.combinat
sage: U3 = DisjointUnionEnumeratedSets(
....:     Family([2,3,4], Permutations, lazy=True))
sage: U3
Disjoint union of Lazy family
 (<class 'sage.combinat.permutation.Permutations'>(i))_{i in [2, 3, 4]}
sage: U3.cardinality()
32
sage: it = iter(U3)
sage: [next(it), next(it), next(it), next(it), next(it), next(it)]
[[1, 2], [2, 1], [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]
sage: U3.unrank(18)
[2, 4, 1, 3]

>>> from sage.all import *
>>> # needs sage.combinat
>>> U3 = DisjointUnionEnumeratedSets(
...     Family([Integer(2),Integer(3),Integer(4)], Permutations, lazy=True))
>>> U3
Disjoint union of Lazy family
 (<class 'sage.combinat.permutation.Permutations'>(i))_{i in [2, 3, 4]}
>>> U3.cardinality()
32
>>> it = iter(U3)
>>> [next(it), next(it), next(it), next(it), next(it), next(it)]
[[1, 2], [2, 1], [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]
>>> U3.unrank(Integer(18))
[2, 4, 1, 3]

This allows for infinite unions:

sage: # needs sage.combinat
sage: U4 = DisjointUnionEnumeratedSets(
....:     Family(NonNegativeIntegers(), Permutations))
sage: U4
Disjoint union of Lazy family
 (<class 'sage.combinat.permutation.Permutations'>(i))_{i in Non negative integers}
sage: U4.cardinality()
+Infinity
sage: it = iter(U4)
sage: [next(it), next(it), next(it), next(it), next(it), next(it)]
[[], [1], [1, 2], [2, 1], [1, 2, 3], [1, 3, 2]]
sage: U4.unrank(18)
[2, 3, 1, 4]

>>> from sage.all import *
>>> # needs sage.combinat
>>> U4 = DisjointUnionEnumeratedSets(
...     Family(NonNegativeIntegers(), Permutations))
>>> U4
Disjoint union of Lazy family
 (<class 'sage.combinat.permutation.Permutations'>(i))_{i in Non negative integers}
>>> U4.cardinality()
+Infinity
>>> it = iter(U4)
>>> [next(it), next(it), next(it), next(it), next(it), next(it)]
[[], [1], [1, 2], [2, 1], [1, 2, 3], [1, 3, 2]]
>>> U4.unrank(Integer(18))
[2, 3, 1, 4]

Warning

Beware that some of the operations assume in that case that infinitely many of the enumerated sets are non empty.

Experimental options

We demonstrate the keepkey option:

sage: # needs sage.combinat
sage: Ukeep = DisjointUnionEnumeratedSets(
....:            Family(list(range(4)), Permutations), keepkey=True)
sage: it = iter(Ukeep)
sage: [next(it) for i in range(6)]
[(0, []), (1, [1]), (2, [1, 2]), (2, [2, 1]), (3, [1, 2, 3]), (3, [1, 3, 2])]
sage: type(next(it)[1])
<class 'sage.combinat.permutation.StandardPermutations_n_with_category.element_class'>

>>> from sage.all import *
>>> # needs sage.combinat
>>> Ukeep = DisjointUnionEnumeratedSets(
...            Family(list(range(Integer(4))), Permutations), keepkey=True)
>>> it = iter(Ukeep)
>>> [next(it) for i in range(Integer(6))]
[(0, []), (1, [1]), (2, [1, 2]), (2, [2, 1]), (3, [1, 2, 3]), (3, [1, 3, 2])]
>>> type(next(it)[Integer(1)])
<class 'sage.combinat.permutation.StandardPermutations_n_with_category.element_class'>

We now demonstrate the facade option:

sage: # needs sage.combinat
sage: UNoFacade = DisjointUnionEnumeratedSets(
....:                Family(list(range(4)), Permutations), facade=False)
sage: it = iter(UNoFacade)
sage: [next(it) for i in range(6)]
[[], [1], [1, 2], [2, 1], [1, 2, 3], [1, 3, 2]]
sage: el = next(it); el
[2, 1, 3]
sage: type(el)
<... 'sage.structure.element_wrapper.ElementWrapper'>
sage: el.parent() == UNoFacade
True
sage: elv = el.value; elv
[2, 1, 3]
sage: type(elv)
<class 'sage.combinat.permutation.StandardPermutations_n_with_category.element_class'>

>>> from sage.all import *
>>> # needs sage.combinat
>>> UNoFacade = DisjointUnionEnumeratedSets(
...                Family(list(range(Integer(4))), Permutations), facade=False)
>>> it = iter(UNoFacade)
>>> [next(it) for i in range(Integer(6))]
[[], [1], [1, 2], [2, 1], [1, 2, 3], [1, 3, 2]]
>>> el = next(it); el
[2, 1, 3]
>>> type(el)
<... 'sage.structure.element_wrapper.ElementWrapper'>
>>> el.parent() == UNoFacade
True
>>> elv = el.value; elv
[2, 1, 3]
>>> type(elv)
<class 'sage.combinat.permutation.StandardPermutations_n_with_category.element_class'>

The elements el of the disjoint union are simple wrapped elements. So to access the methods, you need to do el.value:

sage: el[0]                                                                     # needs sage.combinat
Traceback (most recent call last):
...
TypeError: 'sage.structure.element_wrapper.ElementWrapper' object is not subscriptable

sage: el.value[0]                                                               # needs sage.combinat
2

>>> from sage.all import *
>>> el[Integer(0)]                                                                     # needs sage.combinat
Traceback (most recent call last):
...
TypeError: 'sage.structure.element_wrapper.ElementWrapper' object is not subscriptable

>>> el.value[Integer(0)]                                                               # needs sage.combinat
2

Possible extensions: the current enumeration order is not suitable for unions of infinite enumerated sets (except possibly for the last one). One could add options to specify alternative enumeration orders (anti-diagonal, round robin, …) to handle this case.

Inheriting from DisjointUnionEnumeratedSets

There are two different use cases for inheriting from DisjointUnionEnumeratedSets: writing a parent which happens to be a disjoint union of some known parents, or writing generic disjoint unions for some particular classes of sage.categories.enumerated_sets.EnumeratedSets.

  • In the first use case, the input of the __init__ method is most likely different from that of DisjointUnionEnumeratedSets. Then, one simply writes the __init__ method as usual:

    sage: class MyUnion(DisjointUnionEnumeratedSets):
....:   def __init__(self):
....:       DisjointUnionEnumeratedSets.__init__(self,
....:            Family([1,2], Permutations))
sage: pp = MyUnion()
sage: pp.list()
[[1], [1, 2], [2, 1]]

    >>> from sage.all import *
>>> class MyUnion(DisjointUnionEnumeratedSets):
...   def __init__(self):
...       DisjointUnionEnumeratedSets.__init__(self,
...            Family([Integer(1),Integer(2)], Permutations))
>>> pp = MyUnion()
>>> pp.list()
[[1], [1, 2], [2, 1]]

    In case the __init__() method takes optional arguments, or does some normalization on them, a specific method __classcall_private__ is required (see the documentation of UniqueRepresentation).

  • In the second use case, the input of the __init__ method is the same as that of DisjointUnionEnumeratedSets; one therefore wants to inherit the __classcall_private__() method as well, which can be achieved as follows:

    sage: class UnionOfSpecialSets(DisjointUnionEnumeratedSets):
....:     __classcall_private__ = staticmethod(DisjointUnionEnumeratedSets.__classcall_private__)
sage: psp = UnionOfSpecialSets(Family([1,2], Permutations))
sage: psp.list()
[[1], [1, 2], [2, 1]]

    >>> from sage.all import *
>>> class UnionOfSpecialSets(DisjointUnionEnumeratedSets):
...     __classcall_private__ = staticmethod(DisjointUnionEnumeratedSets.__classcall_private__)
>>> psp = UnionOfSpecialSets(Family([Integer(1),Integer(2)], Permutations))
>>> psp.list()
[[1], [1, 2], [2, 1]]
Element()[source]
an_element()[source]

Return an element of this disjoint union, as per Sets.ParentMethods.an_element().

EXAMPLES:

sage: U4 = DisjointUnionEnumeratedSets(
....:          Family([3, 5, 7], Permutations))
sage: U4.an_element()
[1, 2, 3]

>>> from sage.all import *
>>> U4 = DisjointUnionEnumeratedSets(
...          Family([Integer(3), Integer(5), Integer(7)], Permutations))
>>> U4.an_element()
[1, 2, 3]
cardinality()[source]

Return the cardinality of this disjoint union.

EXAMPLES:

For finite disjoint unions, the cardinality is computed by summing the cardinalities of the enumerated sets:

sage: U = DisjointUnionEnumeratedSets(Family([0,1,2,3], Permutations))
sage: U.cardinality()
10

>>> from sage.all import *
>>> U = DisjointUnionEnumeratedSets(Family([Integer(0),Integer(1),Integer(2),Integer(3)], Permutations))
>>> U.cardinality()
10

For infinite disjoint unions, this makes the assumption that the result is infinite:

sage: U = DisjointUnionEnumeratedSets(
....:         Family(NonNegativeIntegers(), Permutations))
sage: U.cardinality()
+Infinity

>>> from sage.all import *
>>> U = DisjointUnionEnumeratedSets(
...         Family(NonNegativeIntegers(), Permutations))
>>> U.cardinality()
+Infinity

Warning

As pointed out in the main documentation, it is possible to construct examples where this is incorrect:

sage: U = DisjointUnionEnumeratedSets(
....:         Family(NonNegativeIntegers(), lambda x: []))
sage: U.cardinality()  # Should be 0!
+Infinity

>>> from sage.all import *
>>> U = DisjointUnionEnumeratedSets(
...         Family(NonNegativeIntegers(), lambda x: []))
>>> U.cardinality()  # Should be 0!
+Infinity