Enumerated sets#

class sage.categories.enumerated_sets.EnumeratedSets(base_category)[source]#

Bases: CategoryWithAxiom_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 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(): a fresh 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.tuple(): a tuple of the elements of the set, when possible; raises a NotImplementedError if the tuple 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 equivalent 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]

>>> from sage.all import *
>>> EnumeratedSets()
Category of enumerated sets
>>> EnumeratedSets().super_categories()
[Category of sets]
>>> EnumeratedSets().all_super_categories()
[Category of enumerated sets, Category of sets,
 Category of sets with partial maps, Category of objects]
class CartesianProducts(category, *args)[source]#

Bases: CartesianProductsCategory

class ParentMethods[source]#

Bases: object

first()[source]#

Return the first element.

EXAMPLES:

sage: cartesian_product([ZZ]*10).first()
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

>>> from sage.all import *
>>> cartesian_product([ZZ]*Integer(10)).first()
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
class ElementMethods[source]#

Bases: object

rank()[source]#

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)
sage: L[7].rank()
7
sage: all(x.rank() == i for i,x in enumerate(L))
True

>>> from sage.all import *
>>> F = FiniteSemigroups().example(('a','b','c'))
>>> L = list(F)
>>> L[Integer(7)].rank()
7
>>> all(x.rank() == i for i,x in enumerate(L))
True
Finite[source]#

alias of FiniteEnumeratedSets

Infinite[source]#

alias of InfiniteEnumeratedSets

class ParentMethods[source]#

Bases: object

first()[source]#

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

>>> from sage.all import *
>>> C = FiniteEnumeratedSets().example()
>>> C.first() # indirect doctest
1
is_empty()[source]#

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

>>> from sage.all import *
>>> F = FiniteEnumeratedSet([Integer(1),Integer(2),Integer(3)])
>>> F.is_empty()
False
>>> F = FiniteEnumeratedSet([])
>>> F.is_empty()
True
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: # needs sage.combinat
sage: P = Partitions()
sage: list(P.iterator_range(stop=5))
[[], [1], [2], [1, 1], [3]]
sage: list(P.iterator_range(0, 5))
[[], [1], [2], [1, 1], [3]]
sage: list(P.iterator_range(3, 5))
[[1, 1], [3]]
sage: list(P.iterator_range(3, 10))
[[1, 1], [3], [2, 1], [1, 1, 1], [4], [3, 1], [2, 2]]
sage: list(P.iterator_range(3, 10, 2))
[[1, 1], [2, 1], [4], [2, 2]]
sage: it = P.iterator_range(3)
sage: [next(it) for x in range(10)]
[[1, 1],
 [3], [2, 1], [1, 1, 1],
 [4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1],
 [5]]
sage: it = P.iterator_range(3, step=2)
sage: [next(it) for x in range(5)]
[[1, 1],
 [2, 1],
 [4], [2, 2], [1, 1, 1, 1]]
sage: next(P.iterator_range(stop=-3))
Traceback (most recent call last):
...
NotImplementedError: cannot list an infinite set
sage: next(P.iterator_range(start=-3))
Traceback (most recent call last):
...
NotImplementedError: cannot list an infinite set

>>> from sage.all import *
>>> # needs sage.combinat
>>> P = Partitions()
>>> list(P.iterator_range(stop=Integer(5)))
[[], [1], [2], [1, 1], [3]]
>>> list(P.iterator_range(Integer(0), Integer(5)))
[[], [1], [2], [1, 1], [3]]
>>> list(P.iterator_range(Integer(3), Integer(5)))
[[1, 1], [3]]
>>> list(P.iterator_range(Integer(3), Integer(10)))
[[1, 1], [3], [2, 1], [1, 1, 1], [4], [3, 1], [2, 2]]
>>> list(P.iterator_range(Integer(3), Integer(10), Integer(2)))
[[1, 1], [2, 1], [4], [2, 2]]
>>> it = P.iterator_range(Integer(3))
>>> [next(it) for x in range(Integer(10))]
[[1, 1],
 [3], [2, 1], [1, 1, 1],
 [4], [3, 1], [2, 2], [2, 1, 1], [1, 1, 1, 1],
 [5]]
>>> it = P.iterator_range(Integer(3), step=Integer(2))
>>> [next(it) for x in range(Integer(5))]
[[1, 1],
 [2, 1],
 [4], [2, 2], [1, 1, 1, 1]]
>>> next(P.iterator_range(stop=-Integer(3)))
Traceback (most recent call last):
...
NotImplementedError: cannot list an infinite set
>>> next(P.iterator_range(start=-Integer(3)))
Traceback (most recent call last):
...
NotImplementedError: cannot list an infinite set
list()[source]#

Return a list of the elements of self.

The elements of set x are created and cached on the first call of x.list(). Then each call of x.list() returns a new list from the cached result. Thus in looping, it may be better to do for e in x:, not for e in x.list():.

If x is not known to be finite, then an exception is raised.

EXAMPLES:

sage: (GF(3)^2).list()                                                  # needs sage.modules
[(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
sage: R = Integers(11)
sage: R.list()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
sage: l = R.list(); l
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
sage: l.remove(0); l
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
sage: R.list()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

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

>>> from sage.all import *
>>> (GF(Integer(3))**Integer(2)).list()                                                  # needs sage.modules
[(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
>>> R = Integers(Integer(11))
>>> R.list()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> l = R.list(); l
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> l.remove(Integer(0)); l
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> R.list()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

>>> C = FiniteEnumeratedSets().example()
>>> C.list()
[1, 2, 3]
map(f, name, is_injective=None)[source]#

Return the image \(\{f(x) | x \in \text{self}\}\) of this enumerated set by \(f\), as an enumerated set.

INPUT:

  • is_injective – boolean (default: True) whether to assume that f is injective.

EXAMPLES:

sage: R = Compositions(4).map(attrcall('partial_sums')); R
Image of Compositions of 4 by The map *.partial_sums()
 from Compositions of 4
sage: R.cardinality()
8
sage: R.list()
[[1, 2, 3, 4], [1, 2, 4], [1, 3, 4], [1, 4], [2, 3, 4], [2, 4], [3, 4], [4]]
sage: [r for r in R]
[[1, 2, 3, 4], [1, 2, 4], [1, 3, 4], [1, 4], [2, 3, 4], [2, 4], [3, 4], [4]]
sage: R.category()
Category of finite enumerated subobjects of sets

>>> from sage.all import *
>>> R = Compositions(Integer(4)).map(attrcall('partial_sums')); R
Image of Compositions of 4 by The map *.partial_sums()
 from Compositions of 4
>>> R.cardinality()
8
>>> R.list()
[[1, 2, 3, 4], [1, 2, 4], [1, 3, 4], [1, 4], [2, 3, 4], [2, 4], [3, 4], [4]]
>>> [r for r in R]
[[1, 2, 3, 4], [1, 2, 4], [1, 3, 4], [1, 4], [2, 3, 4], [2, 4], [3, 4], [4]]
>>> R.category()
Category of finite enumerated subobjects of sets

Warning

If the function is not injective, then there may be repeated elements:

sage: P = Compositions(4)
sage: P.list()
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]
sage: P.map(attrcall('major_index')).list()
[6, 3, 4, 1, 5, 2, 3, 0]

>>> from sage.all import *
>>> P = Compositions(Integer(4))
>>> P.list()
[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1], [4]]
>>> P.map(attrcall('major_index')).list()
[6, 3, 4, 1, 5, 2, 3, 0]

Pass is_injective=False to get a correct result in this case:

sage: P.map(attrcall('major_index'), is_injective=False).list()
[6, 3, 4, 1, 5, 2, 0]

>>> from sage.all import *
>>> P.map(attrcall('major_index'), is_injective=False).list()
[6, 3, 4, 1, 5, 2, 0]
next(obj)[source]#

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 \(O(r)\), where \(r\) is the rank of obj.

EXAMPLES:

sage: C = InfiniteEnumeratedSets().example()
sage: C._next_from_iterator(10) # indirect doctest
11

>>> from sage.all import *
>>> C = InfiniteEnumeratedSets().example()
>>> C._next_from_iterator(Integer(10)) # indirect doctest
11

TODO: specify the behavior when obj is not in self.

random_element()[source]#

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 raises 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

>>> from sage.all import *
>>> class broken(UniqueRepresentation, Parent):
...  def __init__(self):
...      Parent.__init__(self, category = EnumeratedSets())
>>> broken().random_element()
Traceback (most recent call last):
...
NotImplementedError: unknown cardinality
rank(x)[source]#

The rank of an element of self

self.rank(x) returns the rank of \(x\), 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 \(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 of obj. For infinite enumerated sets, this won’t terminate when \(x\) 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

>>> from sage.all import *
>>> C = FiniteEnumeratedSets().example()
>>> list(C)
[1, 2, 3]
>>> C.rank(Integer(3)) # indirect doctest
2
>>> C.rank(Integer(5)) # indirect doctest
some_elements()[source]#

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 of self

EXAMPLES:

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

>>> from sage.all import *
>>> C = FiniteEnumeratedSets().example()
>>> list(C.some_elements()) # indirect doctest
[1, 2, 3]
tuple()[source]#

Return a tuple of the elements of self.

The tuple of elements of x is created and cached on the first call of x.tuple(). Each following call of x.tuple() returns the same tuple.

For looping, it may be better to do for e in x:, not for e in x.tuple():.

If x is not known to be finite, then an exception is raised.

EXAMPLES:

sage: (GF(3)^2).tuple()                                                 # needs sage.modules
((0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2))
sage: R = Integers(11)
sage: l = R.tuple(); l
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
sage: l is R.tuple()
True

>>> from sage.all import *
>>> (GF(Integer(3))**Integer(2)).tuple()                                                 # needs sage.modules
((0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2))
>>> R = Integers(Integer(11))
>>> l = R.tuple(); l
(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
>>> l is R.tuple()
True
unrank(r)[source]#

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 \(O(r)\), where \(r\) 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 rank must be in the range from 0 to 2
sage: ZZ._unrank_from_iterator(-1)
Traceback (most recent call last):
...
ValueError: the rank must be greater than or equal to 0

>>> from sage.all import *
>>> C = FiniteEnumeratedSets().example()
>>> C.unrank(Integer(2)) # indirect doctest
3
>>> C._unrank_from_iterator(Integer(5))
Traceback (most recent call last):
...
ValueError: the rank must be in the range from 0 to 2
>>> ZZ._unrank_from_iterator(-Integer(1))
Traceback (most recent call last):
...
ValueError: the rank must be greater than or equal to 0
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.

See also

unrank(), iterator_range()

EXAMPLES:

sage: # needs sage.combinat
sage: P = Partitions()
sage: P.unrank_range(stop=5)
[[], [1], [2], [1, 1], [3]]
sage: P.unrank_range(0, 5)
[[], [1], [2], [1, 1], [3]]
sage: P.unrank_range(3, 5)
[[1, 1], [3]]
sage: P.unrank_range(3, 10)
[[1, 1], [3], [2, 1], [1, 1, 1], [4], [3, 1], [2, 2]]
sage: P.unrank_range(3, 10, 2)
[[1, 1], [2, 1], [4], [2, 2]]
sage: P.unrank_range(3)
Traceback (most recent call last):
...
NotImplementedError: cannot list an infinite set
sage: P.unrank_range(stop=-3)
Traceback (most recent call last):
...
NotImplementedError: cannot list an infinite set
sage: P.unrank_range(start=-3)
Traceback (most recent call last):
...
NotImplementedError: cannot list an infinite set

>>> from sage.all import *
>>> # needs sage.combinat
>>> P = Partitions()
>>> P.unrank_range(stop=Integer(5))
[[], [1], [2], [1, 1], [3]]
>>> P.unrank_range(Integer(0), Integer(5))
[[], [1], [2], [1, 1], [3]]
>>> P.unrank_range(Integer(3), Integer(5))
[[1, 1], [3]]
>>> P.unrank_range(Integer(3), Integer(10))
[[1, 1], [3], [2, 1], [1, 1, 1], [4], [3, 1], [2, 2]]
>>> P.unrank_range(Integer(3), Integer(10), Integer(2))
[[1, 1], [2, 1], [4], [2, 2]]
>>> P.unrank_range(Integer(3))
Traceback (most recent call last):
...
NotImplementedError: cannot list an infinite set
>>> P.unrank_range(stop=-Integer(3))
Traceback (most recent call last):
...
NotImplementedError: cannot list an infinite set
>>> P.unrank_range(start=-Integer(3))
Traceback (most recent call last):
...
NotImplementedError: cannot list an infinite set
additional_structure()[source]#

Return None.

Indeed, morphisms of enumerated sets are not required to preserve the enumeration.

See also

Category.additional_structure()

EXAMPLES:

sage: EnumeratedSets().additional_structure()

>>> from sage.all import *
>>> EnumeratedSets().additional_structure()
super_categories()[source]#

EXAMPLES:

sage: EnumeratedSets().super_categories()
[Category of sets]

>>> from sage.all import *
>>> EnumeratedSets().super_categories()
[Category of sets]