Finite Enumerated Sets

class sage.categories.finite_enumerated_sets.FiniteEnumeratedSets(base_category)

Bases: sage.categories.category_with_axiom.CategoryWithAxiom_singleton

The category of finite enumerated sets

EXAMPLES:

sage: FiniteEnumeratedSets()
Category of finite enumerated sets
sage: FiniteEnumeratedSets().super_categories()
[Category of enumerated sets, Category of finite sets]
sage: FiniteEnumeratedSets().all_super_categories()
[Category of finite enumerated sets,
 Category of enumerated sets,
 Category of finite sets,
 Category of sets,
 Category of sets with partial maps,
 Category of objects]

TESTS:

sage: C = FiniteEnumeratedSets()
sage: TestSuite(C).run()
sage: sorted(C.Algebras(QQ).super_categories(), key=str)
[Category of finite dimensional modules with basis over Rational Field,
 Category of set algebras over Rational Field]

Todo

sage.combinat.debruijn_sequence.DeBruijnSequences should not inherit from this class. If that is solved, then FiniteEnumeratedSets shall be turned into a subclass of Category_singleton.

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"
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 ParentMethods
FiniteEnumeratedSets.CartesianProducts.extra_super_categories()

A cartesian product of finite enumerated sets is a finite enumerated set.

EXAMPLES:

sage: C = FiniteEnumeratedSets().CartesianProducts()
sage: C.extra_super_categories()
[Category of finite enumerated sets]
class FiniteEnumeratedSets.IsomorphicObjects(category, *args)

Bases: sage.categories.isomorphic_objects.IsomorphicObjectsCategory

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()
class ParentMethods
cardinality()

Returns the cardinality of self which is the same as that of the ambient set self is isomorphic to.

EXAMPLES:

sage: A = FiniteEnumeratedSets().IsomorphicObjects().example(); A
The image by some isomorphism of An example of a finite enumerated set: {1,2,3}
sage: A.cardinality()
3
FiniteEnumeratedSets.IsomorphicObjects.example()

Returns an example of isomorphic object of a finite enumerated set, as per Category.example.

EXAMPLES:

sage: FiniteEnumeratedSets().IsomorphicObjects().example()
The image by some isomorphism of An example of a finite enumerated set: {1,2,3}
class FiniteEnumeratedSets.ParentMethods
cardinality(*ignored_args, **ignored_kwds)

The cardinality of self.

OUTPUT: an Integer

This brute force implementation of cardinality() iterates through the elements of self to count them.

EXAMPLES:

sage: C = FiniteEnumeratedSets().example(); C
An example of a finite enumerated set: {1,2,3}
sage: C._cardinality_from_iterator()
3

This is the default implementation of cardinality() from the category FiniteEnumeratedSet(). To test this, we need a fresh example:

sage: from sage.categories.examples.finite_enumerated_sets import Example
sage: class FreshExample(Example): pass
sage: C = FreshExample(); C.rename("FreshExample")
sage: C.cardinality
<bound method FreshExample_with_category._cardinality_from_iterator of FreshExample>

TESTS:

This method shall return an Integer; we test this here, because _test_enumerated_set_iter_cardinality() does not do it for us:

sage: type(C._cardinality_from_iterator())
<type 'sage.rings.integer.Integer'>

We ignore additional inputs since during doctests classes which override cardinality() call up to the category rather than their own cardinality() method (see trac ticket #13688):

sage: C = FiniteEnumeratedSets().example()
sage: C._cardinality_from_iterator(algorithm='testing')
3

Here is a more complete example:

sage: class TestParent(Parent):
...     def __init__(self):
...         Parent.__init__(self, category=FiniteEnumeratedSets())
...     def __iter__(self):
...         yield 1
...         return
...     def cardinality(self, dummy_arg):
...         return 1 # we don't want to change the semantics of cardinality()
sage: P = TestParent()
sage: P.cardinality(-1)
1
sage: v = P.list(); v
[1]
sage: P.cardinality()
1
sage: P.cardinality('use alt algorithm') # Used to break here: see :trac:`13688`
1
sage: P.cardinality(dummy_arg='use alg algorithm') # Used to break here: see :trac:`13688`
1
last()

The last element of self.

self.last() returns the last element of self.

This is the default (brute force) implementation from the category FiniteEnumeratedSet() which can be used when the method __iter__ is provided. Its complexity is \(O(n)\) where \(n\) is the size of self.

EXAMPLES:

sage: C = FiniteEnumeratedSets().example()
sage: C.last()
3
sage: C._last_from_iterator()
3
list()

The list of the elements of self.

This default implementation from the category FiniteEnumeratedSet() computes the list of the elements of self from the iterator of self and caches the result. It moreover overrides the following methods to use this cache:

  • self.cardinality()
  • self.__iter__() (but see below)
  • self.unrank()

See also

_list_from_iterator(), _cardinality_from_list(), _iterator_from_list(), and _unrank_from_list()

EXAMPLES:

sage: C = FiniteEnumeratedSets().example()
sage: C.list()
[1, 2, 3]

Warning

The overriding of self.__iter__ to use the cache is ignored upon calls such as for x in C: or list(C) (which essentially ruins its purpose). Indeed, Python looks up the __iter__ method directly in the class of C, bypassing C‘s dictionary (see the Python reference manual, Special method lookup for new-style classes)

Let’s take an example:

sage: class Example(Parent):
...       def __init__(self):
...           Parent.__init__(self, category = FiniteEnumeratedSets())
...       def __iter__(self):
...           print "hello!"
...           for x in [1,2,3]: yield x
sage: C = Example()
sage: list(C)
hello!
hello!
[1, 2, 3]
sage: list(C)
hello!
[1, 2, 3]

Note that hello! actually gets printed twice in the first call to list(C). That’s because of the current (dubious) implementation of Parent.__len__(). Let’s call list():

sage: C.list()
[1, 2, 3]

Now we would want the original iterator of C not to be called anymore, but that’s not the case:

sage: list(C)
hello!
[1, 2, 3]

TESTS:

To test if the caching and overriding works, we need a fresh finite enumerated set example, because the caching mechanism has already been triggered:

sage: from sage.categories.examples.finite_enumerated_sets import Example
sage: class FreshExample(Example): pass
sage: C = FreshExample(); C.rename("FreshExample")
sage: C.list
<bound method FreshExample_with_category.list of FreshExample>
sage: C.unrank
<bound method FreshExample_with_category._unrank_from_iterator of FreshExample>
sage: C.cardinality
<bound method FreshExample_with_category._cardinality_from_iterator of FreshExample>

sage: l1 = C.list(); l1
[1, 2, 3]
sage: C.list
<bound method FreshExample_with_category.list of FreshExample>
sage: C.unrank
<bound method FreshExample_with_category._unrank_from_list of FreshExample>
sage: C.cardinality
<bound method FreshExample_with_category._cardinality_from_list of FreshExample>
sage: C.__iter__
<bound method FreshExample_with_category._iterator_from_list of FreshExample>

We finally check that nothing breaks before and after calling explicitly the method .list():

sage: class FreshExample(Example): pass
sage: import __main__; __main__.FreshExample = FreshExample # Fake FreshExample being defined in a python module
sage: C = FreshExample()
sage: TestSuite(C).run()
sage: C.list()
[1, 2, 3]
sage: TestSuite(C).run()
random_element()

A random element in self.

self.random_element() returns a random element in self with uniform probability.

This is the default implementation from the category EnumeratedSet() which uses the method unrank.

EXAMPLES:

sage: C = FiniteEnumeratedSets().example()
sage: C.random_element()
1
sage: C._random_element_from_unrank()
2

TODO: implement _test_random which checks uniformness

Previous topic

Finite dimensional modules with basis

Next topic

Finite Fields

This Page