# 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.

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(
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'>
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]
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
```