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]

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

class ParentMethods

Bases: object

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 between 0 and n-1 where n is the cardinality of this set.

See also

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 between 0 and n-1 where n is the cardinality of this set.

See also

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
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 IsomorphicObjects(category, *args)

Bases: sage.categories.isomorphic_objects.IsomorphicObjectsCategory

class ParentMethods

Bases: object

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

Bases: object

cardinality(*ignored_args, **ignored_kwds)

Return the cardinality of self.

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
iterator_range(start=None, stop=None, step=None)

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: 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]
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()

Return a list of the elements of self.

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

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]
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: n = C.random_element()
sage: n in C
True

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

TODO: implement _test_random which checks uniformness

unrank_range(start=None, stop=None, step=None)

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

See also unrank().

EXAMPLES:

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

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