Enumerated Sets¶
-
class
sage.categories.enumerated_sets.
EnumeratedSets
(s=None)¶ Bases:
sage.categories.category_singleton.Category_singleton
The category of enumerated sets
An enumerated set is a finite or countable set or multiset \(S\) 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 elements is not supposed to be expanded in memory. Whenever possible one should use one of the two sub-categories
FiniteEnumeratedSets
orInfiniteEnumeratedSets
.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 forlen
on a list except that the return value is specified to be a SageInteger
orinfinity
, instead of a Pythonint
.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)
: then-th
element of the set whenn
is a sageInteger
. This is the equivalent forl[n]
on a list.S.rank(e)
: the position of the elemente
in the set; This is equivalent tol.index(e)
for a list except that the return value is specified to be a SageInteger
, instead of a Pythonint
.S.first()
: the first object of the set; it is equivalent toS.unrank(0)
.S.next(e)
: the object of the set which followse
; It is equivalent toS.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()
-
class
CartesianProducts
(category, *args)¶ Bases:
sage.categories.cartesian_product.CartesianProductsCategory
TESTS:
sage: from sage.categories.covariant_functorial_construction import CovariantConstructionCategory sage: class FooBars(CovariantConstructionCategory): ....: _functor_category = "FooBars" ....: _base_category_class = (Category,) 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()
-
class
EnumeratedSets.
ElementMethods
¶ -
rank
()¶ Return 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', 'b', 'c', 'ac', 'ab', 'ba', 'bc', 'cb', 'ca', 'acb', 'abc', 'bca', 'cba', 'bac', 'cab'] sage: L[7].rank() 7
-
-
EnumeratedSets.
Finite
¶ alias of
FiniteEnumeratedSets
-
EnumeratedSets.
Infinite
¶ alias of
InfiniteEnumeratedSets
-
class
EnumeratedSets.
ParentMethods
¶ -
first
()¶ The “first” element of
self
.self.first()
returns the first element of the setself
. This is a generic implementation from the categoryEnumeratedSets()
which can be used when the method__iter__
is provided.EXAMPLES:
sage: C = FiniteEnumeratedSets().example() sage: C.first() # indirect doctest 1
-
is_empty
()¶ Return whether this set is empty.
EXAMPLES:
sage: F = FiniteEnumeratedSet([1,2,3]) sage: F.is_empty() False sage: F = FiniteEnumeratedSet([]) sage: F.is_empty() True
TESTS:
sage: F.is_empty.__module__ 'sage.categories.enumerated_sets'
-
list
()¶ Return 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
-
map
(f, name=None)¶ Return the image \(\{f(x) | x \in \text{self}\}\) of this enumerated set by \(f\), as an enumerated set.
\(f\) 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() [[], [1], [2, 1], [1, 2], [2], [1, 2, 1]] sage: [ r for r in R] [[], [1], [2, 1], [1, 2], [2], [1, 2, 1]]
Warning
If the function is not injective, then there may be repeated elements:
sage: P = SymmetricGroup(3) sage: P.list() [(), (1,2), (1,2,3), (1,3,2), (2,3), (1,3)] sage: P.map(attrcall('length')).list() [0, 1, 2, 2, 1, 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'])
-
next
(obj)¶ The “next” element after
obj
inself
.self.next(e)
returns the element of the setself
which followse
. This is a generic implementation from the categoryEnumeratedSets()
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 \(O(r)\), where \(r\) is the rank ofobj
.EXAMPLES:
sage: C = InfiniteEnumeratedSets().example() sage: C._next_from_iterator(10) # indirect doctest 11
TODO: specify the behavior when
obj
is not inself
.
-
random_element
()¶ Return 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 aNotImplementedError
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
-
rank
(x)¶ The rank of an element of
self
self.rank(x)
returns the rank of \(x\), that is its position in the enumeration ofself
. This is an integer between0
andn-1
wheren
is the cardinality ofself
, or None if \(x\) is not in \(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 \(O(r)\), where \(r\) is the rank ofobj
. For infinite enumerated sets, this won’t terminate when \(x\) is not inself
EXAMPLES:
sage: C = FiniteEnumeratedSets().example() sage: list(C) [1, 2, 3] sage: C.rank(3) # indirect doctest 2 sage: C.rank(5) # indirect doctest
-
some_elements
()¶ Return 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 ofself
EXAMPLES:
sage: C = FiniteEnumeratedSets().example() sage: list(C.some_elements()) # indirect doctest [1, 2, 3]
-
unrank
(r)¶ The
r
-th element ofself
self.unrank(r)
returns ther
-th element of self, wherer
is an integer between0
andn-1
wheren
is the cardinality ofself
.This is the default (brute force) implementation from the category
EnumeratedSets()
which can be used when the method__iter__
is provided. Its complexity is \(O(r)\), where \(r\) is the rank ofobj
.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
-
-
EnumeratedSets.
additional_structure
()¶ Return
None
.Indeed, morphisms of enumerated sets are not required to preserve the enumeration.
See also
EXAMPLES:
sage: EnumeratedSets().additional_structure()
-
EnumeratedSets.
super_categories
()¶ EXAMPLES:
sage: EnumeratedSets().super_categories() [Category of sets]