Disjoint union of enumerated sets

AUTHORS:

  • Florent Hivert (2009-07/09): initial implementation.
  • Florent Hivert (2010-03): classcall related stuff.
class sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets(family, facade=True, keepkey=False)

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 later 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 (Permutations(i))_{i in [2, 3, 4]}
sage: U3.cardinality()
32
sage: it = iter(U3)
sage: [it.next(), it.next(), it.next(), it.next(), it.next(), it.next()]
[[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 (Permutations(i))_{i in Non negative integers}
sage: U4.cardinality()
+Infinity
sage: it = iter(U4)
sage: [it.next(), it.next(), it.next(), it.next(), it.next(), it.next()]
[[], [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(range(4), Permutations), keepkey=True)
sage: it = iter(Ukeep)
sage: [it.next() for i in range(6)]
[(0, []), (1, [1]), (2, [1, 2]), (2, [2, 1]), (3, [1, 2, 3]), (3, [1, 3, 2])]
sage: type(it.next()[1])
<class 'sage.combinat.permutation.Permutation_class'>

We now demonstrate the facade option:

sage: UNoFacade = DisjointUnionEnumeratedSets(
...                  Family(range(4), Permutations), facade=False)
sage: it = iter(UNoFacade)
sage: [it.next() for i in range(6)]
[[], [1], [1, 2], [2, 1], [1, 2, 3], [1, 3, 2]]
sage: el = it.next(); el
[2, 1, 3]
sage: type(el)
<class 'sage.sets.disjoint_union_enumerated_sets.DisjointUnionEnumeratedSets_with_category.element_class'>
sage: el.parent() == UNoFacade
True
sage: elv = el.value; elv
[2, 1, 3]
sage: type(elv)
<class 'sage.combinat.permutation.Permutation_class'>

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

TESTS:

sage: TestSuite(U1).run()
sage: TestSuite(U2).run()
sage: TestSuite(U3).run()
sage: TestSuite(U4).run()
doctest:...: UserWarning: Disjoint union of Lazy family (Permutations(i))_{i in Non negative integers} is an infinite union
The default implementation of __contains__ can loop forever. Please overload it.
sage: TestSuite(Ukeep).run()
sage: TestSuite(UNoFacade).run()

The following three lines are required for the pickling tests, because the classes MyUnion and UnionOfSpecialSets have been defined interactively:

sage: import __main__
sage: __main__.MyUnion = MyUnion
sage: __main__.UnionOfSpecialSets = UnionOfSpecialSets

sage: TestSuite(pp).run()
sage: TestSuite(psp).run()
class Element(value, parent)
Bases: sage.structure.element_wrapper.ElementWrapper
DisjointUnionEnumeratedSets.an_element()

Returns 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]
DisjointUnionEnumeratedSets.cardinality(*args, **kwds)

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

Previous topic

Disjoint-set data structure

Next topic

Finite Enumerated Sets

This Page