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)

Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent

A class for disjoint unions of enumerated sets.

INPUT:

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

  • keepkey – a boolean

  • facade – a 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

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

However in that case the enumeration order is not specified.

In general the input can be any family:

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]

This allows for infinite unions:

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]

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: 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'>

We now demonstrate the facade option:

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'>

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]  # py2
Traceback (most recent call last):
...
TypeError: 'sage.structure.element_wrapper.ElementWrapper' object
 has no attribute '__getitem__'

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

sage: el.value[0]
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]]

    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]]
Element()
an_element()

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]
cardinality()

Returns 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

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

sage: U = DisjointUnionEnumeratedSets(
....:         Family(NonNegativeIntegers(), Permutations))
sage: 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