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, thenFiniteEnumeratedSets
shall be turned into a subclass ofCategory_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" ....: _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
ParentMethods
¶ TESTS:
Ideally, these tests should be just after the declaration of the associated attributes. But doing this way, Sage will not consider them as a doctest.
We check that Cartesian products of finite enumerated sets inherit various methods from \(Sets.CartesianProducts\) and not from
EnumeratedSets.Finite
:sage: C = cartesian_product([Partitions(10), Permutations(20)]) sage: C in EnumeratedSets().Finite() True sage: C.random_element.__module__ 'sage.categories.sets_cat' sage: C.cardinality.__module__ 'sage.categories.sets_cat' sage: C.__iter__.__module__ 'sage.categories.sets_cat'
-
cardinality
()¶ Return the cardinality of self.
EXAMPLES:
sage: E = FiniteEnumeratedSet([1,2,3]) sage: C = cartesian_product([E,SymmetricGroup(4)]) sage: C.cardinality() 72 sage: E = FiniteEnumeratedSet([]) sage: C = cartesian_product([E, ZZ, QQ]) sage: C.cardinality() 0 sage: C = cartesian_product([ZZ, QQ]) sage: C.cardinality() +Infinity sage: cartesian_product([GF(5), Permutations(10)]).cardinality() 18144000 sage: cartesian_product([GF(71)]*20).cardinality() == 71**20 True
-
last
()¶ Return the last element
EXAMPLES:
sage: C = cartesian_product([Zmod(42), Partitions(10), IntegerRange(5)]) sage: C.last() (41, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 4)
-
random_element
(*args)¶ Return a random element of this Cartesian product.
The extra arguments are passed down to each of the factors of the Cartesian product.
EXAMPLES:
sage: C = cartesian_product([Permutations(10)]*5) sage: C.random_element() # random ([2, 9, 4, 7, 1, 8, 6, 10, 5, 3], [8, 6, 5, 7, 1, 4, 9, 3, 10, 2], [5, 10, 3, 8, 2, 9, 1, 4, 7, 6], [9, 6, 10, 3, 2, 1, 5, 8, 7, 4], [8, 5, 2, 9, 10, 3, 7, 1, 4, 6]) sage: C = cartesian_product([ZZ]*10) sage: c1 = C.random_element() sage: c1 # random (3, 1, 4, 1, 1, -3, 0, -4, -17, 2) sage: c2 = C.random_element(4,7) sage: c2 # random (6, 5, 6, 4, 5, 6, 6, 4, 5, 5) sage: all(4 <= i < 7 for i in c2) True
-
rank
(x)¶ Return the rank of an element of this Cartesian product.
The rank of
x
is its position in the enumeration. It is an integer between0
andn-1
wheren
is the cardinality of this set.EXAMPLES:
sage: C = cartesian_product([GF(2), GF(11), GF(7)]) sage: C.rank(C((1,2,5))) 96 sage: C.rank(C((0,0,0))) 0 sage: for c in C: print(C.rank(c)) 0 1 2 3 4 5 ... 150 151 152 153 sage: F1 = FiniteEnumeratedSet('abcdefgh') sage: F2 = IntegerRange(250) sage: F3 = Partitions(20) sage: C = cartesian_product([F1, F2, F3]) sage: c = C(('a', 86, [7,5,4,4])) sage: C.rank(c) 54213 sage: C.unrank(54213) ('a', 86, [7, 5, 4, 4])
-
unrank
(i)¶ Return the
i
-th element of this Cartesian product.INPUT:
i
– integer between0
andn-1
wheren
is the cardinality of this set.
EXAMPLES:
sage: C = cartesian_product([GF(3), GF(11), GF(7), GF(5)]) sage: c = C.unrank(123); c (0, 3, 3, 3) sage: C.rank(c) 123 sage: c = C.unrank(857); c (2, 2, 3, 2) sage: C.rank(c) 857 sage: C.unrank(2500) Traceback (most recent call last): ... IndexError: index i (=2) is greater than the cardinality
-
-
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
-
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" ....: _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
ParentMethods
¶ -
cardinality
()¶ Returns the cardinality of
self
which is the same as that of the ambient setself
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
-
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 ofself
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 categoryFiniteEnumeratedSet()
. 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 owncardinality()
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 ofself
.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 ofself
.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 ofself
from the iterator ofself
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 asfor x in C:
orlist(C)
(which essentially ruins its purpose). Indeed, Python looks up the__iter__
method directly in the class ofC
, bypassingC
‘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 tolist(C)
. That’s because of the current (dubious) implementation ofParent.__len__()
. Let’s calllist()
: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 inself
with uniform probability.This is the default implementation from the category
EnumeratedSet()
which uses the methodunrank
.EXAMPLES:
sage: C = FiniteEnumeratedSets().example() sage: C.random_element() 1 sage: C._random_element_from_unrank() 2
TODO: implement _test_random which checks uniformness
-
-
class