Bases: sage.categories.category_singleton.Category_singleton
The category of enumerated sets
An enumerated set is a finite or countable set or multiset
together with a canonical enumeration of its elements;
conceptually, this is very similar to an immutable list. The main
difference lies in the names and the return type of the methods,
and of course the fact that the list of element is not supposed to
be expanded in memory. Whenever possible one should use one of the
two sub-categories FiniteEnumeratedSets or
InfiniteEnumeratedSets.
The purpose of this category is threefold:
- to fix a common interface for all these sets;
- to provide a bunch of default implementations;
- to provide consistency tests.
The standard methods for an enumerated set S are:
- S.cardinality(): the number of elements of the set. This is the equivalent for len on a list except that the return value is specified to be a Sage Integer or infinity, instead of a Python int;
- iter(S): an iterator for the elements of the set;
- S.list(): the list of the elements of the set, when possible; raises a NotImplementedError if the list is predictably too large to be expanded in memory.
- S.unrank(n): the n-th element of the set when n is a sage Integer. This is the equivanlent for l[n] on a list.
- S.rank(e): the position of the element e in the set; This is equivalent to l.index(e) for a list except that the return value is specified to be a Sage Integer, instead of a Python int;
- S.first(): the first object of the set; it is equivalent to S.unrank(0);
- S.next(e): the object of the set which follows e; It is equivalent to S.unrank(S.rank(e)+1).
- S.random_element(): a random generator for an element of the set. Unless otherwise stated, and for finite enumerated sets, the probability is uniform.
For examples and tests see:
- FiniteEnumeratedSets().example()
- InfiniteEnumeratedSets().example()
EXAMPLES:
sage: EnumeratedSets()
Category of enumerated sets
sage: EnumeratedSets().super_categories()
[Category of sets]
sage: EnumeratedSets().all_super_categories()
[Category of enumerated sets, Category of sets, Category of sets with partial maps, Category of objects]
TESTS:
sage: C = EnumeratedSets()
sage: TestSuite(C).run()
Bases: sage.categories.cartesian_product.CartesianProductsCategory
TESTS:
sage: from sage.categories.covariant_functorial_construction import CovariantConstructionCategory
sage: class FooBars(CovariantConstructionCategory):
... _functor_category = "FooBars"
sage: Category.FooBars = lambda self: FooBars.category_of(self)
sage: C = FooBars(ModulesWithBasis(ZZ))
sage: C
Category of foo bars of modules with basis over Integer Ring
sage: C.base_category()
Category of modules with basis over Integer Ring
sage: latex(C)
\mathbf{FooBars}(\mathbf{ModulesWithBasis}_{\Bold{Z}})
sage: import __main__; __main__.FooBars = FooBars # Fake FooBars being defined in a python module
sage: TestSuite(C).run()
Returns the rank of self in its parent.
See also EnumeratedSets.ElementMethods.rank()
EXAMPLES:
sage: F = FiniteSemigroups().example(('a','b','c'))
sage: L = list(F); L
['a', 'c', 'ac', 'b', 'ba', 'bc', 'cb', 'ca', 'bca', 'ab', 'bac', 'cab', 'acb', 'cba', 'abc']
sage: L[7].rank()
7
alias of FiniteEnumeratedSets
alias of InfiniteEnumeratedSets
The “first” element of self.
self.first() returns the first element of the set self. This is a generic implementation from the category EnumeratedSets() which can be used when the method __iter__ is provided.
EXAMPLES:
sage: C = FiniteEnumeratedSets().example()
sage: C.first() # indirect doctest
1
Returns an error since the cardinality of self is not known.
EXAMPLES:
sage: class broken(UniqueRepresentation, Parent):
... def __init__(self):
... Parent.__init__(self, category = EnumeratedSets())
...
sage: broken().list()
Traceback (most recent call last):
...
NotImplementedError: unknown cardinality
Returns the image of this
enumerated set by
, as an enumerated set.
is supposed to be injective.
EXAMPLES:
sage: R = SymmetricGroup(3).map(attrcall('reduced_word')); R
Image of Symmetric group of order 3! as a permutation group by *.reduced_word()
sage: R.cardinality()
6
sage: R.list()
[[], [2], [1], [2, 1], [1, 2], [1, 2, 1]]
sage: [ r for r in R]
[[], [2], [1], [2, 1], [1, 2], [1, 2, 1]]
Warning
If the function is not injective, then there may be repeated elements:
sage: P = SymmetricGroup(3)
sage: P.list()
[(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)]
sage: P.map(attrcall('length')).list()
[0, 1, 1, 2, 2, 3]
Warning
MapCombinatorialClass needs to be refactored to use categories:
sage: R.category() # todo: not implemented
Category of enumerated sets
sage: TestSuite(R).run(skip=['_test_an_element', '_test_category', '_test_some_elements'])
The “next” element after obj in self.
self.next(e) returns the element of the set self which follows e. This is a generic implementation from the category EnumeratedSets() which can be used when the method __iter__ is provided.
Remark: this is the default (brute force) implementation
of the category EnumeratedSets(). Its complexity is
, where
is the rank of obj.
EXAMPLES:
sage: C = InfiniteEnumeratedSets().example()
sage: C._next_from_iterator(10) # indirect doctest
11
TODO: specify the behavior when obj is not in self.
Returns a random element in self.
Unless otherwise stated, and for finite enumerated sets, the probability is uniform.
This is a generic implementation from the category EnumeratedSets(). It raise a NotImplementedError since one does not know whether the set is finite.
EXAMPLES:
sage: class broken(UniqueRepresentation, Parent):
... def __init__(self):
... Parent.__init__(self, category = EnumeratedSets())
...
sage: broken().random_element()
Traceback (most recent call last):
...
NotImplementedError: unknown cardinality
The rank of an element of self
self.unrank(x) returns the rank of , that is its
position in the enumeration of self. This is an
integer between 0 and n-1 where n is the
cardinality of self, or None if
is not in
.
This is the default (brute force) implementation from the
category EnumeratedSets() which can be used when the
method __iter__ is provided. Its complexity is ,
where
is the rank of obj. For infinite enumerated
sets, this won’t terminate when
is not in self
EXAMPLES:
sage: C = FiniteEnumeratedSets().example()
sage: list(C)
[1, 2, 3]
sage: C.rank(3) # indirect doctest
2
sage: C.rank(5) # indirect doctest
Returns some elements in self.
See TestSuite for a typical use case.
This is a generic implementation from the category EnumeratedSets() which can be used when the method __iter__ is provided. It returns an iterator for up to the first 100 elements of self
EXAMPLES:
sage: C = FiniteEnumeratedSets().example()
sage: list(C.some_elements()) # indirect doctest
[1, 2, 3]
The r-th element of self
self.unrank(r) returns the r-th element of self where r is an integer between 0 and n-1 where n is the cardinality of self.
This is the default (brute force) implementation from the
category EnumeratedSets() which can be used when the
method __iter__ is provided. Its complexity is ,
where
is the rank of obj.
EXAMPLES:
sage: C = FiniteEnumeratedSets().example()
sage: C.unrank(2) # indirect doctest
3
sage: C._unrank_from_iterator(5)
Traceback (most recent call last):
...
ValueError: the value must be between 0 and 2 inclusive
Return None.
Indeed, morphisms of enumerated sets are not required to preserve the enumeration.
See also
EXAMPLES:
sage: EnumeratedSets().additional_structure()
EXAMPLES:
sage: EnumeratedSets().super_categories()
[Category of sets]