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
sage.sets.set.EnumeratedSet(X)

Return the enumerated set associated to X.

The input object X must be finite.

EXAMPLES:

sage: EnumeratedSet([1,1,2,3])
doctest:1: DeprecationWarning: EnumeratedSet is deprecated; use Set instead.
See http://trac.sagemath.org/8930 for details.
{1, 2, 3}
sage: EnumeratedSet(ZZ)
Traceback (most recent call last):
...
ValueError: X (=Integer Ring) must be finite
sage.sets.set.Set(X)

Create the underlying set of X.

If X is a list, tuple, Python set, or X.is_finite() is True, this returns a wrapper around Python’s enumerated immutable frozenset 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: Set([Sequence([3,1], immutable=True), 5, QQ, Partition([3,1,1])])
{Rational Field, [3, 1, 1], [3, 1], 5}

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: Set(iter([1,2,3]))
{1, 2, 3}
sage: type(_)
<class 'sage.sets.set.Set_object_enumerated_with_category'>
sage: S = Set([])
sage: TestSuite(S).run()
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()

Returns the first element of self returned by __iter__()

If self is empty, the exception EmptySetError is raised instead.

This provides a generic implementation of the method _an_element_() for all parents in EnumeratedSets.

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 and X.

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 if self 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 and X.

EXAMPLES:

sage: X = Set([1,2,3]).symmetric_difference(Set([3,4]))
sage: X
{1, 2, 4}
union(X)

Return the union of self and X.

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_difference(X, Y)

Bases: sage.sets.set.Set_object

Formal difference of two sets.

cardinality()

This tries to return the cardinality of this formal intersection.

Warning

This is not likely to work in very much generality, and may just hang if either set involved is infinite.

EXAMPLES:

sage: X = Set(GF(13)).difference(Set(Primes()))
sage: X.cardinality()
8
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
set([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 and other.

EXAMPLES:

sage: X = Set(GF(8,'c'))
sage: Y = Set([GF(8,'c').0, 1, 2, 3])
sage: X.intersection(Y)
{1, c}
issubset(other)

Return whether self is a subset of other.

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 of other.

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 by set(self.object())? Note that __getitem__() is currently implemented in term of this list method, which is really inefficient ...

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()
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 and other.

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 and other.

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

Formal intersection of two sets.

cardinality()

This tries to return the cardinality of this formal intersection.

Warning

This is not likely to work in very much generality, and may just hang if either set involved is infinite.

EXAMPLES:

sage: X = Set(GF(13)).intersection(Set(ZZ))
sage: X.cardinality()
13
class sage.sets.set.Set_object_symmetric_difference(X, Y)

Bases: sage.sets.set.Set_object

Formal symmetric difference of two sets.

cardinality()

Try to return the cardinality of this formal symmetric difference.

..WARNING:

This is not likely to work in very much generality,
and may just hang if either set involved is infinite.

EXAMPLES:

sage: X = Set(GF(13)).symmetric_difference(Set(range(5)))
sage: X.cardinality()
8
class sage.sets.set.Set_object_union(X, Y)

Bases: sage.sets.set.Set_object

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
sage.sets.set.is_Set(x)

Returns True if x is a Sage Set_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

Previous topic

Families

Next topic

Disjoint-set data structure

This Page