Finite Enumerated Sets#

class sage.categories.finite_enumerated_sets.FiniteEnumeratedSets(base_category)[source]#

Bases: CategoryWithAxiom_singleton

The category of finite enumerated sets

EXAMPLES:

Sage

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]

Python

>>> from sage.all import *
>>> FiniteEnumeratedSets()
Category of finite enumerated sets
>>> FiniteEnumeratedSets().super_categories()
[Category of enumerated sets, Category of finite sets]
>>> 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]

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)[source]#

Bases: CartesianProductsCategory

class ParentMethods[source]#

Bases: object

cardinality()[source]#

Return the cardinality of self.

EXAMPLES:

Sage

sage: E = FiniteEnumeratedSet([1,2,3])
sage: C = cartesian_product([E, SymmetricGroup(4)])                 # needs sage.groups
sage: C.cardinality()                                               # needs sage.groups
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

Python

>>> from sage.all import *
>>> E = FiniteEnumeratedSet([Integer(1),Integer(2),Integer(3)])
>>> C = cartesian_product([E, SymmetricGroup(Integer(4))])                 # needs sage.groups
>>> C.cardinality()                                               # needs sage.groups
72

>>> E = FiniteEnumeratedSet([])
>>> C = cartesian_product([E, ZZ, QQ])
>>> C.cardinality()
0

>>> C = cartesian_product([ZZ, QQ])
>>> C.cardinality()
+Infinity

>>> cartesian_product([GF(Integer(5)), Permutations(Integer(10))]).cardinality()
18144000
>>> cartesian_product([GF(Integer(71))]*Integer(20)).cardinality() == Integer(71)**Integer(20)
True

last()[source]#

Return the last element

EXAMPLES:

Sage

sage: C = cartesian_product([Zmod(42), Partitions(10),              # needs sage.combinat
....:                        IntegerRange(5)])
sage: C.last()                                                      # needs sage.combinat
(41, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 4)

Python

>>> from sage.all import *
>>> C = cartesian_product([Zmod(Integer(42)), Partitions(Integer(10)),              # needs sage.combinat
...                        IntegerRange(Integer(5))])
>>> C.last()                                                      # needs sage.combinat
(41, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 4)

random_element(*args)[source]#

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

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

Python

>>> from sage.all import *
>>> C = cartesian_product([Permutations(Integer(10))]*Integer(5))
>>> 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])

>>> C = cartesian_product([ZZ]*Integer(10))
>>> c1 = C.random_element()
>>> c1                   # random
(3, 1, 4, 1, 1, -3, 0, -4, -17, 2)
>>> c2 = C.random_element(Integer(4),Integer(7))
>>> c2                   # random
(6, 5, 6, 4, 5, 6, 6, 4, 5, 5)
>>> all(Integer(4) <= i < Integer(7) for i in c2)
True

rank(x)[source]#

Return the rank of an element of this Cartesian product.

The rank of x is its position in the enumeration. It is an integer between 0 and n-1 where n is the cardinality of this set.

See also

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> C = cartesian_product([GF(Integer(3)), GF(Integer(11)), GF(Integer(7)), GF(Integer(5))])
>>> c = C.unrank(Integer(123)); c
(0, 3, 3, 3)
>>> C.rank(c)
123

>>> c = C.unrank(Integer(857)); c
(2, 2, 3, 2)
>>> C.rank(c)
857

>>> C.unrank(Integer(2500))
Traceback (most recent call last):
...
IndexError: index i (=2) is greater than the cardinality

extra_super_categories()[source]#

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

EXAMPLES:

Sage

sage: C = FiniteEnumeratedSets().CartesianProducts()
sage: C.extra_super_categories()
[Category of finite enumerated sets]

Python

>>> from sage.all import *
>>> C = FiniteEnumeratedSets().CartesianProducts()
>>> C.extra_super_categories()
[Category of finite enumerated sets]

class IsomorphicObjects(category, *args)[source]#

Bases: IsomorphicObjectsCategory

class ParentMethods[source]#

Bases: object

cardinality()[source]#

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

EXAMPLES:

Sage

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

Python

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

example()[source]#

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

EXAMPLES:

Sage

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

Python

>>> from sage.all import *
>>> FiniteEnumeratedSets().IsomorphicObjects().example()
The image by some isomorphism of An example of a finite enumerated set: {1,2,3}

class ParentMethods[source]#

Bases: object

cardinality(*ignored_args, **ignored_kwds)[source]#

Return the cardinality of self.

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

EXAMPLES:

Sage

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

Python

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

iterator_range(start=None, stop=None, step=None)[source]#

Iterate over the range of elements of self starting at start, ending at stop, and stepping by step.

See also

unrank(), unrank_range()

EXAMPLES:

Sage

sage: F = FiniteEnumeratedSet([1,2,3])
sage: list(F.iterator_range(1))
[2, 3]
sage: list(F.iterator_range(stop=2))
[1, 2]
sage: list(F.iterator_range(stop=2, step=2))
[1]
sage: list(F.iterator_range(start=1, step=2))
[2]
sage: list(F.iterator_range(start=1, stop=2))
[2]
sage: list(F.iterator_range(start=0, stop=1))
[1]
sage: list(F.iterator_range(start=0, stop=3, step=2))
[1, 3]
sage: list(F.iterator_range(stop=-1))
[1, 2]

sage: F = FiniteEnumeratedSet([1,2,3,4])
sage: list(F.iterator_range(start=1, stop=3))
[2, 3]
sage: list(F.iterator_range(stop=10))
[1, 2, 3, 4]

Python

>>> from sage.all import *
>>> F = FiniteEnumeratedSet([Integer(1),Integer(2),Integer(3)])
>>> list(F.iterator_range(Integer(1)))
[2, 3]
>>> list(F.iterator_range(stop=Integer(2)))
[1, 2]
>>> list(F.iterator_range(stop=Integer(2), step=Integer(2)))
[1]
>>> list(F.iterator_range(start=Integer(1), step=Integer(2)))
[2]
>>> list(F.iterator_range(start=Integer(1), stop=Integer(2)))
[2]
>>> list(F.iterator_range(start=Integer(0), stop=Integer(1)))
[1]
>>> list(F.iterator_range(start=Integer(0), stop=Integer(3), step=Integer(2)))
[1, 3]
>>> list(F.iterator_range(stop=-Integer(1)))
[1, 2]

>>> F = FiniteEnumeratedSet([Integer(1),Integer(2),Integer(3),Integer(4)])
>>> list(F.iterator_range(start=Integer(1), stop=Integer(3)))
[2, 3]
>>> list(F.iterator_range(stop=Integer(10)))
[1, 2, 3, 4]

last()[source]#

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

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

Python

>>> from sage.all import *
>>> C = FiniteEnumeratedSets().example()
>>> C.last()
3
>>> C._last_from_iterator()
3

random_element()[source]#

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

sage: C = FiniteEnumeratedSets().example()
sage: n = C.random_element()
sage: n in C
True

sage: n = C._random_element_from_unrank()
sage: n in C
True

Python

>>> from sage.all import *
>>> C = FiniteEnumeratedSets().example()
>>> n = C.random_element()
>>> n in C
True

>>> n = C._random_element_from_unrank()
>>> n in C
True

TODO: implement _test_random which checks uniformness

tuple()[source]#

Return a tuple`of the elements of ``self`.

EXAMPLES:

Sage

sage: C = FiniteEnumeratedSets().example()
sage: C.tuple()
(1, 2, 3)
sage: C.tuple() is C.tuple()
True

Python

>>> from sage.all import *
>>> C = FiniteEnumeratedSets().example()
>>> C.tuple()
(1, 2, 3)
>>> C.tuple() is C.tuple()
True

unrank_range(start=None, stop=None, step=None)[source]#

Return the range of elements of self starting at start, ending at stop, and stepping by step.