Sets¶
AUTHORS:
- William Stein (2005) - first version
- William Stein (2006-02-16) - large number of documentation and examples; improved code
- Mike Hansen (2007-3-25) - added differences and symmetric differences; fixed operators
- Florent Hivert (2010-06-17) - Adapted to categories
- Nicolas M. Thiery (2011-03-15) - Added subset and superset methods
- Julian Rueth (2013-04-09) - Collected common code in
Set_object_binary
, fixed__hash__
.
-
sage.sets.set.
Set
(X=frozenset([]))¶ Create the underlying set of
X
.If
X
is a list, tuple, Python set, orX.is_finite()
isTrue
, this returns a wrapper around Python’s enumerated immutablefrozenset
type with extra functionality. Otherwise it returns a more formal wrapper.If you need the functionality of mutable sets, use Python’s builtin set type.
EXAMPLES:
sage: X = Set(GF(9,'a')) sage: X {0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2} sage: type(X) <class 'sage.sets.set.Set_object_enumerated_with_category'> sage: Y = X.union(Set(QQ)) sage: Y Set-theoretic union of {0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2} and Set of elements of Rational Field sage: type(Y) <class 'sage.sets.set.Set_object_union_with_category'>
Usually sets can be used as dictionary keys.
sage: d={Set([2*I,1+I]):10} sage: d # key is randomly ordered {{I + 1, 2*I}: 10} sage: d[Set([1+I,2*I])] 10 sage: d[Set((1+I,2*I))] 10
The original object is often forgotten.
sage: v = [1,2,3] sage: X = Set(v) sage: X {1, 2, 3} sage: v.append(5) sage: X {1, 2, 3} sage: 5 in X False
Set also accepts iterators, but be careful to only give finite sets.
sage: list(Set(iter([1, 2, 3, 4, 5]))) [1, 2, 3, 4, 5]
We can also create sets from different types:
sage: sorted(Set([Sequence([3,1], immutable=True), 5, QQ, Partition([3,1,1])]), key=str) [5, Rational Field, [3, 1, 1], [3, 1]]
However each of the objects must be hashable:
sage: Set([QQ, [3, 1], 5]) Traceback (most recent call last): ... TypeError: unhashable type: 'list'
TESTS:
sage: Set(Primes()) Set of all prime numbers: 2, 3, 5, 7, ... sage: Set(Subsets([1,2,3])).cardinality() 8 sage: S = Set(iter([1,2,3])); S {1, 2, 3} sage: type(S) <class 'sage.sets.set.Set_object_enumerated_with_category'> sage: S = Set([]) sage: TestSuite(S).run()
Check that trac ticket #16090 is fixed:
sage: Set() {}
-
class
sage.sets.set.
Set_object
(X)¶ Bases:
sage.structure.parent.Set_generic
A set attached to an almost arbitrary object.
EXAMPLES:
sage: K = GF(19) sage: Set(K) {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18} sage: S = Set(K) sage: latex(S) \left\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18\right\} sage: TestSuite(S).run() sage: latex(Set(ZZ)) \Bold{Z}
TESTS:
See trac ticket trac ticket #14486:
sage: 0 == Set([1]), Set([1]) == 0 (False, False) sage: 1 == Set([0]), Set([0]) == 1 (False, False)
-
an_element
()¶ Return the first element of
self
returned by__iter__()
If
self
is empty, the exceptionEmptySetError
is raised instead.This provides a generic implementation of the method
_an_element_()
for all parents inEnumeratedSets
.EXAMPLES:
sage: C = FiniteEnumeratedSets().example(); C An example of a finite enumerated set: {1,2,3} sage: C.an_element() # indirect doctest 1 sage: S = Set([]) sage: S.an_element() Traceback (most recent call last): ... EmptySetError
TESTS:
sage: super(Parent, C)._an_element_ Cached version of <function _an_element_from_iterator at ...>
-
cardinality
()¶ Return the cardinality of this set, which is either an integer or
Infinity
.EXAMPLES:
sage: Set(ZZ).cardinality() +Infinity sage: Primes().cardinality() +Infinity sage: Set(GF(5)).cardinality() 5 sage: Set(GF(5^2,'a')).cardinality() 25
-
difference
(X)¶ Return the set difference
self - X
.EXAMPLES:
sage: X = Set(ZZ).difference(Primes()) sage: 4 in X True sage: 3 in X False sage: 4/1 in X True sage: X = Set(GF(9,'b')).difference(Set(GF(27,'c'))) sage: X {0, 1, 2, b, b + 1, b + 2, 2*b, 2*b + 1, 2*b + 2} sage: X = Set(GF(9,'b')).difference(Set(GF(27,'b'))) sage: X {0, 1, 2, b, b + 1, b + 2, 2*b, 2*b + 1, 2*b + 2}
-
intersection
(X)¶ Return the intersection of
self
andX
.EXAMPLES:
sage: X = Set(ZZ).intersection(Primes()) sage: 4 in X False sage: 3 in X True sage: 2/1 in X True sage: X = Set(GF(9,'b')).intersection(Set(GF(27,'c'))) sage: X {} sage: X = Set(GF(9,'b')).intersection(Set(GF(27,'b'))) sage: X {}
-
is_empty
()¶ Return boolean representing emptiness of the set.
OUTPUT:
True if the set is empty, false if otherwise.
EXAMPLES:
sage: Set([]).is_empty() True sage: Set([0]).is_empty() False sage: Set([1..100]).is_empty() False sage: Set(SymmetricGroup(2).list()).is_empty() False sage: Set(ZZ).is_empty() False
TESTS:
sage: Set([]).is_empty() True sage: Set([1,2,3]).is_empty() False sage: Set([1..100]).is_empty() False sage: Set(DihedralGroup(4).list()).is_empty() False sage: Set(QQ).is_empty() False
-
is_finite
()¶ Return
True
ifself
is finite.EXAMPLES:
sage: Set(QQ).is_finite() False sage: Set(GF(250037)).is_finite() True sage: Set(Integers(2^1000000)).is_finite() True sage: Set([1,'a',ZZ]).is_finite() True
-
object
()¶ Return underlying object.
EXAMPLES:
sage: X = Set(QQ) sage: X.object() Rational Field sage: X = Primes() sage: X.object() Set of all prime numbers: 2, 3, 5, 7, ...
-
subsets
(size=None)¶ Return the
Subsets
object representing the subsets of a set. If size is specified, return the subsets of that size.EXAMPLES:
sage: X = Set([1,2,3]) sage: list(X.subsets()) [{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}] sage: list(X.subsets(2)) [{1, 2}, {1, 3}, {2, 3}]
-
symmetric_difference
(X)¶ Returns the symmetric difference of
self
andX
.EXAMPLES:
sage: X = Set([1,2,3]).symmetric_difference(Set([3,4])) sage: X {1, 2, 4}
-
union
(X)¶ Return the union of
self
andX
.EXAMPLES:
sage: Set(QQ).union(Set(ZZ)) Set-theoretic union of Set of elements of Rational Field and Set of elements of Integer Ring sage: Set(QQ) + Set(ZZ) Set-theoretic union of Set of elements of Rational Field and Set of elements of Integer Ring sage: X = Set(QQ).union(Set(GF(3))); X Set-theoretic union of Set of elements of Rational Field and {0, 1, 2} sage: 2/3 in X True sage: GF(3)(2) in X True sage: GF(5)(2) in X False sage: Set(GF(7)) + Set(GF(3)) {0, 1, 2, 3, 4, 5, 6, 1, 2, 0}
-
-
class
sage.sets.set.
Set_object_binary
(X, Y, op, latex_op)¶ Bases:
sage.sets.set.Set_object
An abstract common base class for sets defined by a binary operation (ex.
Set_object_union
,Set_object_intersection
,Set_object_difference
, andSet_object_symmetric_difference
).INPUT:
X
,Y
– sets, the operands toop
op
– a string describing the binary operationlatex_op
– a string used for rendering this object in LaTeX
EXAMPLES:
sage: X = Set(QQ^2) sage: Y = Set(ZZ) sage: from sage.sets.set import Set_object_binary sage: S = Set_object_binary(X, Y, "union", "\\cup"); S Set-theoretic union of Set of elements of Vector space of dimension 2 over Rational Field and Set of elements of Integer Ring
-
class
sage.sets.set.
Set_object_difference
(X, Y)¶ Bases:
sage.sets.set.Set_object_binary
Formal difference of two sets.
-
is_finite
()¶ Return whether this set is finite.
EXAMPLES:
sage: X = Set(range(10)) sage: Y = Set(range(-10,5)) sage: Z = Set(QQ) sage: X.difference(Y).is_finite() True sage: X.difference(Z).is_finite() True sage: Z.difference(X).is_finite() False sage: Z.difference(Set(ZZ)).is_finite() Traceback (most recent call last): ... NotImplementedError
-
-
class
sage.sets.set.
Set_object_enumerated
(X)¶ Bases:
sage.sets.set.Set_object
A finite enumerated set.
-
cardinality
()¶ Return the cardinality of
self
.EXAMPLES:
sage: Set([1,1]).cardinality() 1
-
difference
(other)¶ Return the set difference
self - other
.EXAMPLES:
sage: X = Set([1,2,3,4]) sage: Y = Set([1,2]) sage: X.difference(Y) {3, 4} sage: Z = Set(ZZ) sage: W = Set([2.5, 4, 5, 6]) sage: W.difference(Z) {2.50000000000000}
-
frozenset
()¶ Return the Python frozenset object associated to this set, which is an immutable set (hence hashable).
EXAMPLES:
sage: X = Set(GF(8,'c')) sage: X {0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1} sage: s = X.set(); s {0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1} sage: hash(s) Traceback (most recent call last): ... TypeError: unhashable type: 'set' sage: s = X.frozenset(); s frozenset({0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1}) sage: hash(s) -1390224788 # 32-bit 561411537695332972 # 64-bit sage: type(s) <type 'frozenset'>
-
intersection
(other)¶ Return the intersection of
self
andother
.EXAMPLES:
sage: X = Set(GF(8,'c')) sage: Y = Set([GF(8,'c').0, 1, 2, 3]) sage: X.intersection(Y) {1, c}
-
is_finite
()¶ Return
True
as this is a finite set.EXAMPLES:
sage: Set(GF(19)).is_finite() True
-
issubset
(other)¶ Return whether
self
is a subset ofother
.INPUT:
other
– a finite Set
EXAMPLES:
sage: X = Set([1,3,5]) sage: Y = Set([0,1,2,3,5,7]) sage: X.issubset(Y) True sage: Y.issubset(X) False sage: X.issubset(X) True
TESTS:
sage: len([Z for Z in Y.subsets() if Z.issubset(X)]) 8
-
issuperset
(other)¶ Return whether
self
is a superset ofother
.INPUT:
other
– a finite Set
EXAMPLES:
sage: X = Set([1,3,5]) sage: Y = Set([0,1,2,3,5]) sage: X.issuperset(Y) False sage: Y.issuperset(X) True sage: X.issuperset(X) True
TESTS:
sage: len([Z for Z in Y.subsets() if Z.issuperset(X)]) 4
-
list
()¶ Return the elements of
self
, as a list.EXAMPLES:
sage: X = Set(GF(8,'c')) sage: X {0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1} sage: X.list() [0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1] sage: type(X.list()) <type 'list'>
Todo
FIXME: What should be the order of the result? That of
self.object()
? Or the order given byset(self.object())
? Note that__getitem__()
is currently implemented in term of this list method, which is really inefficient ...
-
random_element
()¶ Return a random element in this set.
EXAMPLES:
sage: Set([1,2,3]).random_element() # random 2
-
set
()¶ Return the Python set object associated to this set.
Python has a notion of finite set, and often Sage sets have an associated Python set. This function returns that set.
EXAMPLES:
sage: X = Set(GF(8,'c')) sage: X {0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1} sage: X.set() {0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1} sage: type(X.set()) <type 'set'> sage: type(X) <class 'sage.sets.set.Set_object_enumerated_with_category'>
-
symmetric_difference
(other)¶ Return the symmetric difference of
self
andother
.EXAMPLES:
sage: X = Set([1,2,3,4]) sage: Y = Set([1,2]) sage: X.symmetric_difference(Y) {3, 4} sage: Z = Set(ZZ) sage: W = Set([2.5, 4, 5, 6]) sage: U = W.symmetric_difference(Z) sage: 2.5 in U True sage: 4 in U False sage: V = Z.symmetric_difference(W) sage: V == U True sage: 2.5 in V True sage: 6 in V False
-
union
(other)¶ Return the union of
self
andother
.EXAMPLES:
sage: X = Set(GF(8,'c')) sage: Y = Set([GF(8,'c').0, 1, 2, 3]) sage: X {0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1} sage: Y {1, c, 3, 2} sage: X.union(Y) {0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1, 2, 3}
-
-
class
sage.sets.set.
Set_object_intersection
(X, Y)¶ Bases:
sage.sets.set.Set_object_binary
Formal intersection of two sets.
-
is_finite
()¶ Return whether this set is finite.
EXAMPLES:
sage: X = Set(IntegerRange(100)) sage: Y = Set(ZZ) sage: X.intersection(Y).is_finite() True sage: Y.intersection(X).is_finite() True sage: Y.intersection(Set(QQ)).is_finite() Traceback (most recent call last): ... NotImplementedError
-
-
class
sage.sets.set.
Set_object_symmetric_difference
(X, Y)¶ Bases:
sage.sets.set.Set_object_binary
Formal symmetric difference of two sets.
-
is_finite
()¶ Return whether this set is finite.
EXAMPLES:
sage: X = Set(range(10)) sage: Y = Set(range(-10,5)) sage: Z = Set(QQ) sage: X.symmetric_difference(Y).is_finite() True sage: X.symmetric_difference(Z).is_finite() False sage: Z.symmetric_difference(X).is_finite() False sage: Z.symmetric_difference(Set(ZZ)).is_finite() Traceback (most recent call last): ... NotImplementedError
-
-
class
sage.sets.set.
Set_object_union
(X, Y)¶ Bases:
sage.sets.set.Set_object_binary
A formal union of two sets.
-
cardinality
()¶ Return the cardinality of this set.
EXAMPLES:
sage: X = Set(GF(3)).union(Set(GF(2))) sage: X {0, 1, 2, 0, 1} sage: X.cardinality() 5 sage: X = Set(GF(3)).union(Set(ZZ)) sage: X.cardinality() +Infinity
-
is_finite
()¶ Return whether this set is finite.
EXAMPLES:
sage: X = Set(range(10)) sage: Y = Set(range(-10,0)) sage: Z = Set(Primes()) sage: X.union(Y).is_finite() True sage: X.union(Z).is_finite() False
-
-
sage.sets.set.
is_Set
(x)¶ Returns
True
ifx
is a SageSet_object
(not to be confused with a Python set).EXAMPLES:
sage: from sage.sets.set import is_Set sage: is_Set([1,2,3]) False sage: is_Set(set([1,2,3])) False sage: is_Set(Set([1,2,3])) True sage: is_Set(Set(QQ)) True sage: is_Set(Primes()) True