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:
UniqueRepresentation
,Parent
A class for disjoint unions of enumerated sets.
INPUT:
family
– a list (or iterable or family) of enumerated setskeepkey
– a booleanfacade
– 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 (seesage.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)
wherekey
is the index of the set to whichel
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 thevalue
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: # 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]
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]
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'>
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'>
The elements
el
of the disjoint union are simple wrapped elements. So to access the methods, you need to doel.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
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 ofsage.categories.enumerated_sets.EnumeratedSets
.In the first use case, the input of the
__init__
method is most likely different from that ofDisjointUnionEnumeratedSets
. 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 ofUniqueRepresentation
).In the second use case, the input of the
__init__
method is the same as that ofDisjointUnionEnumeratedSets
; 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