Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
sagemath
GitHub Repository: sagemath/sagelib
Path: blob/master/sage/sets/set.py
4045 views
1
"""
2
Sets
3
4
AUTHORS:
5
6
- William Stein (2005) - first version
7
8
- William Stein (2006-02-16) - large number of documentation and
9
examples; improved code
10
11
- Mike Hansen (2007-3-25) - added differences and symmetric
12
differences; fixed operators
13
14
- Florent Hivert (2010-06-17) - Adapted to categories
15
16
- Nicolas M. Thiery (2011-03-15) - Added subset and superset methods
17
"""
18
19
#*****************************************************************************
20
# Copyright (C) 2005 William Stein <[email protected]>
21
#
22
# Distributed under the terms of the GNU General Public License (GPL)
23
#
24
# This code is distributed in the hope that it will be useful,
25
# but WITHOUT ANY WARRANTY; without even the implied warranty of
26
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
27
# General Public License for more details.
28
#
29
# The full text of the GPL is available at:
30
#
31
# http://www.gnu.org/licenses/
32
#*****************************************************************************
33
34
from sage.structure.element import Element
35
from sage.structure.parent import Parent, Set_generic
36
from sage.misc.latex import latex
37
import sage.rings.infinity
38
from sage.misc.misc import is_iterator
39
from sage.categories.sets_cat import Sets
40
from sage.categories.enumerated_sets import EnumeratedSets
41
42
def Set(X):
43
r"""
44
Create the underlying set of $X$.
45
46
If $X$ is a list, tuple, Python set, or ``X.is_finite()`` is
47
true, this returns a wrapper around Python's enumerated immutable
48
frozenset type with extra functionality. Otherwise it returns a
49
more formal wrapper.
50
51
If you need the functionality of mutable sets, use Python's
52
builtin set type.
53
54
EXAMPLES::
55
56
sage: X = Set(GF(9,'a'))
57
sage: X
58
{0, 1, 2, a, a + 1, a + 2, 2*a, 2*a + 1, 2*a + 2}
59
sage: type(X)
60
<class 'sage.sets.set.Set_object_enumerated_with_category'>
61
sage: Y = X.union(Set(QQ))
62
sage: Y
63
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
64
sage: type(Y)
65
<class 'sage.sets.set.Set_object_union_with_category'>
66
67
Usually sets can be used as dictionary keys.
68
69
::
70
71
sage: d={Set([2*I,1+I]):10}
72
sage: d # key is randomly ordered
73
{{I + 1, 2*I}: 10}
74
sage: d[Set([1+I,2*I])]
75
10
76
sage: d[Set((1+I,2*I))]
77
10
78
79
The original object is often forgotten.
80
81
::
82
83
sage: v = [1,2,3]
84
sage: X = Set(v)
85
sage: X
86
{1, 2, 3}
87
sage: v.append(5)
88
sage: X
89
{1, 2, 3}
90
sage: 5 in X
91
False
92
93
Set also accepts iterators, but be careful to only give *finite* sets.
94
95
::
96
97
sage: list(Set(iter([1, 2, 3, 4, 5])))
98
[1, 2, 3, 4, 5]
99
100
TESTS::
101
102
sage: Set(Primes())
103
Set of all prime numbers: 2, 3, 5, 7, ...
104
sage: Set(Subsets([1,2,3])).cardinality()
105
8
106
sage: Set(iter([1,2,3]))
107
{1, 2, 3}
108
sage: type(_)
109
<class 'sage.sets.set.Set_object_enumerated_with_category'>
110
sage: S = Set([])
111
sage: TestSuite(S).run()
112
"""
113
if is_Set(X):
114
return X
115
116
if isinstance(X, Element):
117
raise TypeError, "Element has no defined underlying set"
118
elif isinstance(X, (list, tuple, set, frozenset)):
119
return Set_object_enumerated(frozenset(X))
120
try:
121
if X.is_finite():
122
return Set_object_enumerated(X)
123
except AttributeError:
124
pass
125
if is_iterator(X):
126
# Note we are risking an infinite loop here,
127
# but this is the way Python behaves too: try
128
# sage: set(an iterator which does not terminate)
129
return Set_object_enumerated(list(X))
130
return Set_object(X)
131
132
def EnumeratedSet(X):
133
"""
134
Return the enumerated set associated to $X$.
135
136
The input object $X$ must be finite.
137
138
EXAMPLES::
139
140
sage: EnumeratedSet([1,1,2,3])
141
doctest:1: DeprecationWarning: EnumeratedSet is deprecated; use Set instead.
142
{1, 2, 3}
143
sage: EnumeratedSet(ZZ)
144
Traceback (most recent call last):
145
...
146
ValueError: X (=Integer Ring) must be finite
147
"""
148
from sage.misc.misc import deprecation
149
deprecation('EnumeratedSet is deprecated; use Set instead.')
150
try:
151
if not X.is_finite():
152
raise ValueError, "X (=%s) must be finite"%X
153
except AttributeError:
154
pass
155
return Set_object_enumerated(X)
156
157
def is_Set(x):
158
"""
159
Returns true if $x$ is a Sage Set (not to be confused with
160
a Python 2.4 set).
161
162
EXAMPLES::
163
164
sage: from sage.sets.set import is_Set
165
sage: is_Set([1,2,3])
166
False
167
sage: is_Set(set([1,2,3]))
168
False
169
sage: is_Set(Set([1,2,3]))
170
True
171
sage: is_Set(Set(QQ))
172
True
173
sage: is_Set(Primes())
174
True
175
"""
176
return isinstance(x, Set_generic)
177
178
class Set_object(Set_generic):
179
r"""
180
A set attached to an almost arbitrary object.
181
182
EXAMPLES::
183
184
sage: K = GF(19)
185
sage: Set(K)
186
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}
187
sage: S = Set(K)
188
189
sage: latex(S)
190
\left\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18\right\}
191
sage: TestSuite(S).run()
192
193
sage: latex(Set(ZZ))
194
\Bold{Z}
195
"""
196
def __init__(self, X):
197
"""
198
Create a Set_object
199
200
This function is called by the Set function; users
201
shouldn't call this directly.
202
203
EXAMPLES::
204
205
sage: type(Set(QQ))
206
<class 'sage.sets.set.Set_object_with_category'>
207
"""
208
Parent.__init__(self, category=Sets())
209
self.__object = X
210
211
def __hash__(self):
212
return hash(self.__object)
213
214
def _latex_(self):
215
r"""
216
Return latex representation of this set.
217
218
This is often the same as the latex representation of this
219
object when the object is infinite.
220
221
EXAMPLES::
222
223
sage: latex(Set(QQ))
224
\Bold{Q}
225
226
When the object is finite or a special set then the latex
227
representation can be more interesting.
228
229
::
230
231
sage: print latex(Primes())
232
\verb|Set...of...all...prime...numbers:...|
233
sage: print latex(Set([1,1,1,5,6]))
234
\left\{1, 5, 6\right\}
235
"""
236
return latex(self.__object)
237
238
def _repr_(self):
239
"""
240
Print representation of this set.
241
242
EXAMPLES::
243
244
sage: X = Set(ZZ)
245
sage: X
246
Set of elements of Integer Ring
247
sage: X.rename('{ integers }')
248
sage: X
249
{ integers }
250
"""
251
return "Set of elements of %s"%self.__object
252
253
def __iter__(self):
254
"""
255
Iterate over the elements of this set.
256
257
EXAMPLES::
258
259
sage: X = Set(ZZ)
260
sage: I = X.__iter__()
261
sage: I.next()
262
0
263
sage: I.next()
264
1
265
sage: I.next()
266
-1
267
sage: I.next()
268
2
269
"""
270
return self.__object.__iter__()
271
272
an_element = EnumeratedSets.ParentMethods.__dict__['_an_element_from_iterator']
273
274
def __contains__(self, x):
275
"""
276
Return True if $x$ is in self.
277
278
EXAMPLES::
279
280
sage: X = Set(ZZ)
281
sage: 5 in X
282
True
283
sage: GF(7)(3) in X
284
True
285
sage: 2/1 in X
286
True
287
sage: 2/1 in ZZ
288
True
289
sage: 2/3 in X
290
False
291
292
Finite fields better illustrate the difference between
293
__contains__ for objects and their underlying sets.
294
295
sage: X = Set(GF(7))
296
sage: X
297
{0, 1, 2, 3, 4, 5, 6}
298
sage: 5/3 in X
299
False
300
sage: 5/3 in GF(7)
301
False
302
sage: Set(GF(7)).union(Set(GF(5)))
303
{0, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 0}
304
sage: Set(GF(7)).intersection(Set(GF(5)))
305
{}
306
"""
307
return x in self.__object
308
309
def __cmp__(self, right):
310
r"""
311
Compare self and right.
312
313
If right is not a Set compare types. If right is also a Set,
314
returns comparison on the underlying objects.
315
316
.. note::
317
318
If `X < Y` is true this does *not* necessarily mean
319
that `X` is a subset of `Y`. Also, any two sets can be
320
compared still, but the result need not be meaningful
321
if they are not equal.
322
323
EXAMPLES:
324
sage: Set(ZZ) == Set(QQ)
325
False
326
sage: Set(ZZ) < Set(QQ)
327
True
328
sage: Primes() == Set(QQ)
329
False
330
331
The following is random, illustrating that comparison of
332
sets is not the subset relation, when they are not equal::
333
334
sage: Primes() < Set(QQ) # random
335
True or False
336
"""
337
if not isinstance(right, Set_object):
338
return cmp(type(self), type(right))
339
return cmp(self.__object, right.__object)
340
341
def union(self, X):
342
"""
343
Return the union of self and X.
344
345
EXAMPLES::
346
347
sage: Set(QQ).union(Set(ZZ))
348
Set-theoretic union of Set of elements of Rational Field and Set of elements of Integer Ring
349
sage: Set(QQ) + Set(ZZ)
350
Set-theoretic union of Set of elements of Rational Field and Set of elements of Integer Ring
351
sage: X = Set(QQ).union(Set(GF(3))); X
352
Set-theoretic union of Set of elements of Rational Field and {0, 1, 2}
353
sage: 2/3 in X
354
True
355
sage: GF(3)(2) in X
356
True
357
sage: GF(5)(2) in X
358
False
359
sage: Set(GF(7)) + Set(GF(3))
360
{0, 1, 2, 3, 4, 5, 6, 1, 2, 0}
361
"""
362
if is_Set(X):
363
if self is X:
364
return self
365
return Set_object_union(self, X)
366
raise TypeError, "X (=%s) must be a Set"%X
367
368
def __add__(self, X):
369
"""
370
Return the union of self and X.
371
372
EXAMPLES::
373
374
sage: Set(RealField()) + Set(QQ^5)
375
Set-theoretic union of Set of elements of Real Field with 53 bits of precision and Set of elements of Vector space of dimension 5 over Rational Field
376
sage: Set(GF(3)) + Set(GF(2))
377
{0, 1, 2, 0, 1}
378
sage: Set(GF(2)) + Set(GF(4,'a'))
379
{0, 1, a, a + 1}
380
sage: Set(GF(8,'b')) + Set(GF(4,'a'))
381
{0, 1, b, b + 1, b^2, b^2 + 1, b^2 + b, b^2 + b + 1, a, a + 1, 1, 0}
382
"""
383
return self.union(X)
384
385
def __or__(self, X):
386
"""
387
Return the union of self and X.
388
389
EXAMPLES::
390
391
sage: Set([2,3]) | Set([3,4])
392
{2, 3, 4}
393
sage: Set(ZZ) | Set(QQ)
394
Set-theoretic union of Set of elements of Integer Ring and Set of elements of Rational Field
395
"""
396
397
return self.union(X)
398
399
def intersection(self, X):
400
r"""
401
Return the intersection of self and X.
402
403
EXAMPLES::
404
405
sage: X = Set(ZZ).intersection(Primes())
406
sage: 4 in X
407
False
408
sage: 3 in X
409
True
410
411
sage: 2/1 in X
412
True
413
414
sage: X = Set(GF(9,'b')).intersection(Set(GF(27,'c')))
415
sage: X
416
{}
417
418
sage: X = Set(GF(9,'b')).intersection(Set(GF(27,'b')))
419
sage: X
420
{}
421
"""
422
if is_Set(X):
423
if self is X:
424
return self
425
return Set_object_intersection(self, X)
426
raise TypeError, "X (=%s) must be a Set"%X
427
428
429
def difference(self, X):
430
r"""
431
Return the intersection of self and X.
432
433
EXAMPLES::
434
435
sage: X = Set(ZZ).difference(Primes())
436
sage: 4 in X
437
True
438
sage: 3 in X
439
False
440
441
sage: 4/1 in X
442
True
443
444
sage: X = Set(GF(9,'b')).difference(Set(GF(27,'c')))
445
sage: X
446
{0, 1, 2, b, b + 1, b + 2, 2*b, 2*b + 1, 2*b + 2}
447
448
sage: X = Set(GF(9,'b')).difference(Set(GF(27,'b')))
449
sage: X
450
{0, 1, 2, b, b + 1, b + 2, 2*b, 2*b + 1, 2*b + 2}
451
"""
452
if is_Set(X):
453
if self is X:
454
return Set([])
455
return Set_object_difference(self, X)
456
raise TypeError, "X (=%s) must be a Set"%X
457
458
def symmetric_difference(self, X):
459
r"""
460
Returns the symmetric difference of self and X.
461
462
EXAMPLES::
463
464
sage: X = Set([1,2,3]).symmetric_difference(Set([3,4]))
465
sage: X
466
{1, 2, 4}
467
"""
468
469
if is_Set(X):
470
if self is X:
471
return Set([])
472
return Set_object_symmetric_difference(self, X)
473
raise TypeError, "X (=%s) must be a Set"%X
474
475
476
def __sub__(self, X):
477
"""
478
Return the difference of self and X.
479
480
EXAMPLES::
481
482
sage: X = Set(ZZ).difference(Primes())
483
sage: Y = Set(ZZ) - Primes()
484
sage: X == Y
485
True
486
"""
487
return self.difference(X)
488
489
def __and__(self, X):
490
"""
491
Returns the intersection of self and X.
492
493
EXAMPLES::
494
495
sage: Set([2,3]) & Set([3,4])
496
{3}
497
sage: Set(ZZ) & Set(QQ)
498
Set-theoretic intersection of Set of elements of Integer Ring and Set of elements of Rational Field
499
"""
500
501
return self.intersection(X)
502
503
def __xor__(self, X):
504
"""
505
Returns the symmetric difference of self and X.
506
507
EXAMPLES::
508
509
sage: X = Set([1,2,3,4])
510
sage: Y = Set([1,2])
511
sage: X.symmetric_difference(Y)
512
{3, 4}
513
sage: X.__xor__(Y)
514
{3, 4}
515
"""
516
return self.symmetric_difference(X)
517
518
def cardinality(self):
519
"""
520
Return the cardinality of this set, which is either an integer or Infinity.
521
522
EXAMPLES::
523
524
sage: Set(ZZ).cardinality()
525
+Infinity
526
sage: Primes().cardinality()
527
+Infinity
528
sage: Set(GF(5)).cardinality()
529
5
530
sage: Set(GF(5^2,'a')).cardinality()
531
25
532
"""
533
try:
534
if not self.is_finite():
535
return sage.rings.infinity.infinity
536
except AttributeError:
537
pass
538
try:
539
return self.__object.cardinality()
540
except AttributeError:
541
pass
542
try:
543
return len(self.__object)
544
except TypeError:
545
raise NotImplementedError, "computation of cardinality of %s not yet implemented"%self.__object
546
547
def is_finite(self):
548
"""
549
EXAMPLES::
550
551
sage: Set(QQ).is_finite()
552
False
553
sage: Set(GF(250037)).is_finite()
554
True
555
sage: Set(Integers(2^1000000)).is_finite()
556
True
557
sage: Set([1,'a',ZZ]).is_finite()
558
True
559
"""
560
if isinstance(self.__object, (set, frozenset, tuple, list)):
561
return True
562
else:
563
return self.__object.is_finite()
564
565
def object(self):
566
"""
567
Return underlying object.
568
569
EXAMPLES::
570
571
sage: X = Set(QQ)
572
sage: X.object()
573
Rational Field
574
sage: X = Primes()
575
sage: X.object()
576
Set of all prime numbers: 2, 3, 5, 7, ...
577
"""
578
return self.__object
579
580
581
def subsets(self,size=None):
582
"""
583
Return the Subset object representing the subsets of a set. If size
584
is specified, return the subsets of that size.
585
586
EXAMPLES::
587
588
sage: X = Set([1,2,3])
589
sage: list(X.subsets())
590
[{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}]
591
sage: list(X.subsets(2))
592
[{1, 2}, {1, 3}, {2, 3}]
593
594
"""
595
from sage.combinat.subset import Subsets
596
return Subsets(self,size)
597
598
class Set_object_enumerated(Set_object):
599
"""
600
A finite enumerated set.
601
"""
602
def __init__(self, X):
603
"""
604
EXAMPLES::
605
606
sage: S = Set(GF(19)); S
607
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18}
608
sage: print latex(S)
609
\left\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18\right\}
610
sage: TestSuite(S).run()
611
"""
612
Set_object.__init__(self, X)
613
614
def cardinality(self):
615
"""
616
EXAMPLES::
617
618
sage: Set([1,1]).cardinality()
619
1
620
"""
621
return len(self.set())
622
623
def __len__(self):
624
"""
625
EXAMPLES::
626
627
sage: len(Set([1,1]))
628
1
629
"""
630
return self.cardinality()
631
632
633
def __iter__(self):
634
r"""
635
Iterating through the elements of ``self``.
636
637
EXAMPLES::
638
639
sage: S = Set(GF(19))
640
sage: I = iter(S)
641
sage: I.next()
642
0
643
sage: I.next()
644
1
645
sage: I.next()
646
2
647
sage: I.next()
648
3
649
"""
650
for x in self.set():
651
yield x
652
653
def _latex_(self):
654
r"""
655
Return the LaTeX representation of ``self``.
656
657
EXAMPLES::
658
659
sage: S = Set(GF(2))
660
sage: latex(S)
661
\left\{0, 1\right\}
662
"""
663
return '\\left\\{' + ', '.join([latex(x) for x in self.set()]) + '\\right\\}'
664
665
def _repr_(self):
666
r"""
667
Return the string representation of ``self``.
668
669
EXAMPLES::
670
671
sage: S = Set(GF(2))
672
sage: S
673
{0, 1}
674
"""
675
s = repr(self.set())
676
return "{" + s[5:-2] + "}"
677
678
def list(self):
679
"""
680
Return the elements of self, as a list.
681
682
EXAMPLES::
683
684
sage: X = Set(GF(8,'c'))
685
sage: X
686
{0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1}
687
sage: X.list()
688
[0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1]
689
sage: type(X.list())
690
<type 'list'>
691
692
FIXME: What should be the order of the result?
693
That of self.object()? Or the order given by set(self.object())?
694
Note that :meth:`__getitem__` is currently implemented in term
695
of this list method, which is really inefficient ...
696
"""
697
return list(set(self.object()))
698
699
def set(self):
700
"""
701
Return the Python set object associated to this set.
702
703
Python has a notion of finite set, and often Sage sets
704
have an associated Python set. This function returns
705
that set.
706
707
EXAMPLES::
708
709
sage: X = Set(GF(8,'c'))
710
sage: X
711
{0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1}
712
sage: X.set()
713
set([0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1])
714
sage: type(X.set())
715
<type 'set'>
716
sage: type(X)
717
<class 'sage.sets.set.Set_object_enumerated_with_category'>
718
"""
719
return set(self.object())
720
721
def frozenset(self):
722
"""
723
Return the Python frozenset object associated to this set,
724
which is an immutable set (hence hashable).
725
726
EXAMPLES::
727
728
sage: X = Set(GF(8,'c'))
729
sage: X
730
{0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1}
731
sage: s = X.set(); s
732
set([0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1])
733
sage: hash(s)
734
Traceback (most recent call last):
735
...
736
TypeError: unhashable type: 'set'
737
sage: s = X.frozenset(); s
738
frozenset([0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1])
739
sage: hash(s)
740
-1390224788 # 32-bit
741
561411537695332972 # 64-bit
742
sage: type(s)
743
<type 'frozenset'>
744
"""
745
return frozenset(self.object())
746
747
def __hash__(self):
748
return hash(self.frozenset())
749
750
def __cmp__(self, other):
751
"""
752
Compare the sets self and other.
753
754
EXAMPLES:
755
sage: X = Set(GF(8,'c'))
756
sage: X == Set(GF(8,'c'))
757
True
758
sage: X == Set(GF(4,'a'))
759
False
760
sage: Set(QQ) == Set(ZZ)
761
False
762
"""
763
if isinstance(other, Set_object_enumerated):
764
if self.set() == other.set():
765
return 0
766
return -1
767
else:
768
return Set_object.__cmp__(self, other)
769
770
def issubset(self, other):
771
r"""
772
Inclusion test
773
774
- ``other`` -- a finite Set
775
776
Returns whether ``self`` is a subset of ``other``
777
778
EXAMPLES::
779
780
sage: X = Set([1,3,5])
781
sage: Y = Set([0,1,2,3,5,7])
782
sage: X.issubset(Y)
783
True
784
sage: Y.issubset(X)
785
False
786
sage: X.issubset(X)
787
True
788
789
TESTS::
790
791
sage: len([Z for Z in Y.subsets() if Z.issubset(X)])
792
8
793
"""
794
if not isinstance(other, Set_object_enumerated):
795
raise NotImplementedError
796
return self.set().issubset(other.set())
797
798
def issuperset(self, other):
799
r"""
800
Reverse inclusion test
801
802
- ``other`` -- a finite Set
803
804
Returns whether ``self`` is a superset of ``other``
805
806
EXAMPLES::
807
808
sage: X = Set([1,3,5])
809
sage: Y = Set([0,1,2,3,5])
810
sage: X.issuperset(Y)
811
False
812
sage: Y.issuperset(X)
813
True
814
sage: X.issuperset(X)
815
True
816
817
TESTS::
818
819
sage: len([Z for Z in Y.subsets() if Z.issuperset(X)])
820
4
821
"""
822
if not isinstance(other, Set_object_enumerated):
823
raise NotImplementedError
824
return self.set().issuperset(other.set())
825
826
def union(self, other):
827
"""
828
Return the union of self and other.
829
830
EXAMPLES::
831
832
sage: X = Set(GF(8,'c'))
833
sage: Y = Set([GF(8,'c').0, 1, 2, 3])
834
sage: X
835
{0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1}
836
sage: Y
837
{1, c, 3, 2}
838
sage: X.union(Y)
839
{0, 1, c, c + 1, c^2, c^2 + 1, c^2 + c, c^2 + c + 1, 2, 3}
840
"""
841
if not isinstance(other, Set_object_enumerated):
842
return Set_object.union(self, other)
843
return Set_object_enumerated(self.set().union(other.set()))
844
845
def intersection(self, other):
846
"""
847
Return the intersection of self and other.
848
849
EXAMPLES::
850
851
sage: X = Set(GF(8,'c'))
852
sage: Y = Set([GF(8,'c').0, 1, 2, 3])
853
sage: X.intersection(Y)
854
{1, c}
855
"""
856
if not isinstance(other, Set_object_enumerated):
857
return Set_object.intersection(self, other)
858
return Set_object_enumerated(self.set().intersection(other.set()))
859
860
def difference(self, other):
861
"""
862
Returns the set difference self-other.
863
864
EXAMPLES::
865
866
sage: X = Set([1,2,3,4])
867
sage: Y = Set([1,2])
868
sage: X.difference(Y)
869
{3, 4}
870
sage: Z = Set(ZZ)
871
sage: W = Set([2.5, 4, 5, 6])
872
sage: W.difference(Z)
873
{2.50000000000000}
874
"""
875
if not isinstance(other, Set_object_enumerated):
876
return Set([x for x in self if x not in other])
877
return Set_object_enumerated(self.set().difference(other.set()))
878
879
def symmetric_difference(self, other):
880
"""
881
Returns the set difference self-other.
882
883
EXAMPLES::
884
885
sage: X = Set([1,2,3,4])
886
sage: Y = Set([1,2])
887
sage: X.symmetric_difference(Y)
888
{3, 4}
889
sage: Z = Set(ZZ)
890
sage: W = Set([2.5, 4, 5, 6])
891
sage: U = W.symmetric_difference(Z)
892
sage: 2.5 in U
893
True
894
sage: 4 in U
895
False
896
sage: V = Z.symmetric_difference(W)
897
sage: V == U
898
True
899
sage: 2.5 in V
900
True
901
sage: 6 in V
902
False
903
"""
904
if not isinstance(other, Set_object_enumerated):
905
return Set_object.symmetric_difference(self, other)
906
return Set_object_enumerated(self.set().symmetric_difference(other.set()))
907
908
class Set_object_union(Set_object):
909
"""
910
A formal union of two sets.
911
"""
912
def __init__(self, X, Y):
913
r"""
914
EXAMPLES::
915
916
sage: S = Set(QQ^2)
917
sage: T = Set(ZZ)
918
sage: X = S.union(T); X
919
Set-theoretic union of Set of elements of Vector space of dimension 2 over Rational Field and Set of elements of Integer Ring
920
921
sage: latex(X)
922
\Bold{Q}^{2} \cup \Bold{Z}
923
924
sage: TestSuite(X).run()
925
"""
926
self.__X = X
927
self.__Y = Y
928
Set_object.__init__(self, self)
929
930
def __cmp__(self, right):
931
r"""
932
Try to compare self and right.
933
934
.. note::
935
936
Comparison is basically not implemented, or rather it could
937
say sets are not equal even though they are. I don't know
938
how one could implement this for a generic union of sets in
939
a meaningful manner. So be careful when using this.
940
941
EXAMPLES::
942
943
sage: Y = Set(ZZ^2).union(Set(ZZ^3))
944
sage: X = Set(ZZ^3).union(Set(ZZ^2))
945
sage: X == Y
946
True
947
sage: Y == X
948
True
949
950
This illustrates that equality testing for formal unions
951
can be misleading in general.
952
953
::
954
955
sage: Set(ZZ).union(Set(QQ)) == Set(QQ)
956
False
957
"""
958
if not is_Set(right):
959
return -1
960
if not isinstance(right, Set_object_union):
961
return -1
962
if self.__X == right.__X and self.__Y == right.__Y or \
963
self.__X == right.__Y and self.__Y == right.__X:
964
return 0
965
return -1
966
967
def _repr_(self):
968
r"""
969
Return string representation of self.
970
971
EXAMPLES::
972
973
sage: Set(ZZ).union(Set(GF(5)))
974
Set-theoretic union of Set of elements of Integer Ring and {0, 1, 2, 3, 4}
975
"""
976
return "Set-theoretic union of %s and %s"%(self.__X,
977
self.__Y)
978
979
def _latex_(self):
980
r"""
981
Return latex representation of self.
982
983
EXAMPLES::
984
985
sage: latex(Set(ZZ).union(Set(GF(5))))
986
\Bold{Z} \cup \left\{0, 1, 2, 3, 4\right\}
987
"""
988
return '%s \\cup %s'%(latex(self.__X), latex(self.__Y))
989
990
def __iter__(self):
991
"""
992
Return iterator over the elements of self.
993
994
EXAMPLES::
995
996
sage: [x for x in Set(GF(3)).union(Set(GF(2)))]
997
[0, 1, 2, 0, 1]
998
"""
999
for x in self.__X:
1000
yield x
1001
for y in self.__Y:
1002
yield y
1003
1004
def __contains__(self, x):
1005
"""
1006
Returns True if x is an element of self.
1007
1008
EXAMPLES::
1009
1010
sage: X = Set(GF(3)).union(Set(GF(2)))
1011
sage: GF(5)(1) in X
1012
False
1013
sage: GF(3)(2) in X
1014
True
1015
sage: GF(2)(0) in X
1016
True
1017
sage: GF(5)(0) in X
1018
False
1019
"""
1020
return x in self.__X or x in self.__Y
1021
1022
def cardinality(self):
1023
"""
1024
Return the cardinality of this set.
1025
1026
EXAMPLES::
1027
1028
sage: X = Set(GF(3)).union(Set(GF(2)))
1029
sage: X
1030
{0, 1, 2, 0, 1}
1031
sage: X.cardinality()
1032
5
1033
1034
sage: X = Set(GF(3)).union(Set(ZZ))
1035
sage: X.cardinality()
1036
+Infinity
1037
"""
1038
return self.__X.cardinality() + self.__Y.cardinality()
1039
1040
class Set_object_intersection(Set_object):
1041
"""
1042
Formal intersection of two sets.
1043
"""
1044
def __init__(self, X, Y):
1045
r"""
1046
EXAMPLES::
1047
1048
sage: S = Set(QQ^2)
1049
sage: T = Set(ZZ)
1050
sage: X = S.intersection(T); X
1051
Set-theoretic intersection of Set of elements of Vector space of dimension 2 over Rational Field and Set of elements of Integer Ring
1052
sage: latex(X)
1053
\Bold{Q}^{2} \cap \Bold{Z}
1054
1055
sage: X = Set(IntegerRange(100)).intersection(Primes())
1056
sage: TestSuite(X).run()
1057
"""
1058
self.__X = X
1059
self.__Y = Y
1060
Set_object.__init__(self, self)
1061
1062
1063
def __cmp__(self, right):
1064
r"""
1065
Try to compare self and right.
1066
1067
.. note::
1068
1069
Comparison is basically not implemented, or rather it could
1070
say sets are not equal even though they are. I don't know
1071
how one could implement this for a generic intersection of
1072
sets in a meaningful manner. So be careful when using
1073
this.
1074
1075
EXAMPLES:
1076
sage: Y = Set(ZZ).intersection(Set(QQ))
1077
sage: X = Set(QQ).intersection(Set(ZZ))
1078
sage: X == Y
1079
True
1080
sage: Y == X
1081
True
1082
1083
This illustrates that equality testing for formal unions
1084
can be misleading in general.
1085
1086
::
1087
1088
sage: Set(ZZ).intersection(Set(QQ)) == Set(QQ)
1089
False
1090
"""
1091
if not is_Set(right):
1092
return -1
1093
if not isinstance(right, Set_object_intersection):
1094
return -1
1095
if self.__X == right.__X and self.__Y == right.__Y or \
1096
self.__X == right.__Y and self.__Y == right.__X:
1097
return 0
1098
return -1
1099
1100
def _repr_(self):
1101
"""
1102
Return string representation of self.
1103
1104
EXAMPLES::
1105
1106
sage: X = Set(ZZ).intersection(Set(QQ)); X
1107
Set-theoretic intersection of Set of elements of Integer Ring and Set of elements of Rational Field
1108
sage: X.rename('Z /\ Q')
1109
sage: X
1110
Z /\ Q
1111
"""
1112
return "Set-theoretic intersection of %s and %s"%(self.__X,
1113
self.__Y)
1114
1115
def _latex_(self):
1116
r"""
1117
Return latex representation of self.
1118
1119
EXAMPLES::
1120
1121
sage: X = Set(ZZ).intersection(Set(QQ))
1122
sage: latex(X)
1123
\Bold{Z} \cap \Bold{Q}
1124
"""
1125
return '%s \\cap %s'%(latex(self.__X), latex(self.__Y))
1126
1127
def __iter__(self):
1128
"""
1129
Return iterator through elements of self.
1130
1131
Self is a formal intersection of X and Y and this function is
1132
implemented by iterating through the elements of X and for
1133
each checking if it is in Y, and if yielding it.
1134
1135
EXAMPLES::
1136
1137
sage: X = Set(ZZ).intersection(Primes())
1138
sage: I = X.__iter__()
1139
sage: I.next()
1140
2
1141
"""
1142
for x in self.__X:
1143
if x in self.__Y:
1144
yield x
1145
1146
def __contains__(self, x):
1147
"""
1148
Return true if self contains x.
1149
1150
Since self is a formal intersection of X and Y this function
1151
returns true if both X and Y contains x.
1152
1153
EXAMPLES::
1154
1155
sage: X = Set(QQ).intersection(Set(RR))
1156
sage: 5 in X
1157
True
1158
sage: ComplexField().0 in X
1159
False
1160
1161
Any specific floating-point number in Sage is to finite precision, hence it is rational::
1162
1163
sage: RR(sqrt(2)) in X
1164
True
1165
1166
Real constants are not rational::
1167
1168
sage: pi in X
1169
False
1170
"""
1171
return x in self.__X and x in self.__Y
1172
1173
def cardinality(self):
1174
"""
1175
This tries to return the cardinality of this formal intersection.
1176
1177
Note that this is not likely to work in very much generality,
1178
and may just hang if either set involved is infinite.
1179
1180
EXAMPLES::
1181
1182
sage: X = Set(GF(13)).intersection(Set(ZZ))
1183
sage: X.cardinality()
1184
13
1185
"""
1186
return len(list(self))
1187
1188
1189
1190
class Set_object_difference(Set_object):
1191
"""
1192
Formal difference of two sets.
1193
"""
1194
def __init__(self, X, Y):
1195
r"""
1196
EXAMPLES::
1197
1198
sage: S = Set(QQ)
1199
sage: T = Set(ZZ)
1200
sage: X = S.difference(T); X
1201
Set-theoretic difference between Set of elements of Rational Field and Set of elements of Integer Ring
1202
sage: latex(X)
1203
\Bold{Q} - \Bold{Z}
1204
1205
sage: TestSuite(X).run()
1206
"""
1207
self.__X = X
1208
self.__Y = Y
1209
Set_object.__init__(self, self)
1210
1211
1212
def __cmp__(self, right):
1213
r"""
1214
Try to compare self and right.
1215
1216
.. note::
1217
1218
Comparison is basically not implemented, or rather it could
1219
say sets are not equal even though they are. I don't know
1220
how one could implement this for a generic intersection of
1221
sets in a meaningful manner. So be careful when using
1222
this.
1223
1224
EXAMPLES::
1225
1226
sage: Y = Set(ZZ).difference(Set(QQ))
1227
sage: Y == Set([])
1228
False
1229
sage: X = Set(QQ).difference(Set(ZZ))
1230
sage: Y == X
1231
False
1232
sage: Z = X.difference(Set(ZZ))
1233
sage: Z == X
1234
False
1235
1236
This illustrates that equality testing for formal unions
1237
can be misleading in general.
1238
1239
::
1240
1241
sage: X == Set(QQ).difference(Set(ZZ))
1242
True
1243
"""
1244
if not is_Set(right):
1245
return -1
1246
if not isinstance(right, Set_object_difference):
1247
return -1
1248
if self.__X == right.__X and self.__Y == right.__Y:
1249
return 0
1250
return -1
1251
1252
def _repr_(self):
1253
"""
1254
Return string representation of self.
1255
1256
EXAMPLES::
1257
1258
sage: X = Set(QQ).difference(Set(ZZ)); X
1259
Set-theoretic difference between Set of elements of Rational Field and Set of elements of Integer Ring
1260
sage: X.rename('Q - Z')
1261
sage: X
1262
Q - Z
1263
"""
1264
return "Set-theoretic difference between %s and %s"%(self.__X,
1265
self.__Y)
1266
1267
def _latex_(self):
1268
r"""
1269
Return latex representation of self.
1270
1271
EXAMPLES::
1272
1273
sage: X = Set(QQ).difference(Set(ZZ))
1274
sage: latex(X)
1275
\Bold{Q} - \Bold{Z}
1276
"""
1277
return '%s - %s'%(latex(self.__X), latex(self.__Y))
1278
1279
def __iter__(self):
1280
"""
1281
Return iterator through elements of self.
1282
1283
Self is a formal difference of X and Y and this function is
1284
implemented by iterating through the elements of X and for
1285
each checking if it is not in Y, and if yielding it.
1286
1287
EXAMPLES::
1288
1289
sage: X = Set(ZZ).difference(Primes())
1290
sage: I = X.__iter__()
1291
sage: I.next()
1292
0
1293
sage: I.next()
1294
1
1295
sage: I.next()
1296
-1
1297
sage: I.next()
1298
-2
1299
sage: I.next()
1300
-3
1301
"""
1302
for x in self.__X:
1303
if x not in self.__Y:
1304
yield x
1305
1306
def __contains__(self, x):
1307
"""
1308
Return true if self contains x.
1309
1310
Since self is a formal intersection of X and Y this function
1311
returns true if both X and Y contains x.
1312
1313
EXAMPLES::
1314
1315
sage: X = Set(QQ).difference(Set(ZZ))
1316
sage: 5 in X
1317
False
1318
sage: ComplexField().0 in X
1319
False
1320
sage: sqrt(2) in X # since sqrt(2) is not a numerical approx
1321
False
1322
sage: sqrt(RR(2)) in X # since sqrt(RR(2)) is a numerical approx
1323
True
1324
sage: 5/2 in X
1325
True
1326
"""
1327
return x in self.__X and x not in self.__Y
1328
1329
def cardinality(self):
1330
"""
1331
This tries to return the cardinality of this formal intersection.
1332
1333
Note that this is not likely to work in very much generality,
1334
and may just hang if either set involved is infinite.
1335
1336
EXAMPLES::
1337
1338
sage: X = Set(GF(13)).difference(Set(Primes()))
1339
sage: X.cardinality()
1340
8
1341
"""
1342
return len(list(self))
1343
1344
class Set_object_symmetric_difference(Set_object):
1345
"""
1346
Formal symmetric difference of two sets.
1347
"""
1348
def __init__(self, X, Y):
1349
r"""
1350
EXAMPLES::
1351
1352
sage: S = Set(QQ)
1353
sage: T = Set(ZZ)
1354
sage: X = S.symmetric_difference(T); X
1355
Set-theoretic symmetric difference of Set of elements of Rational Field and Set of elements of Integer Ring
1356
sage: latex(X)
1357
\Bold{Q} \bigtriangleup \Bold{Z}
1358
1359
sage: TestSuite(X).run()
1360
"""
1361
self.__X = X
1362
self.__Y = Y
1363
Set_object.__init__(self, self)
1364
1365
1366
def __cmp__(self, right):
1367
r"""
1368
Try to compare self and right.
1369
1370
.. note::
1371
1372
Comparison is basically not implemented, or rather it could
1373
say sets are not equal even though they are. I don't know
1374
how one could implement this for a generic symmetric
1375
difference of sets in a meaningful manner. So be careful
1376
when using this.
1377
1378
EXAMPLES::
1379
1380
sage: Y = Set(ZZ).symmetric_difference(Set(QQ))
1381
sage: X = Set(QQ).symmetric_difference(Set(ZZ))
1382
sage: X == Y
1383
True
1384
sage: Y == X
1385
True
1386
1387
"""
1388
if not is_Set(right):
1389
return -1
1390
if not isinstance(right, Set_object_symmetric_difference):
1391
return -1
1392
if self.__X == right.__X and self.__Y == right.__Y or \
1393
self.__X == right.__Y and self.__Y == right.__X:
1394
return 0
1395
return -1
1396
1397
def _repr_(self):
1398
"""
1399
Return string representation of self.
1400
1401
EXAMPLES::
1402
1403
sage: X = Set(ZZ).symmetric_difference(Set(QQ)); X
1404
Set-theoretic symmetric difference of Set of elements of Integer Ring and Set of elements of Rational Field
1405
sage: X.rename('Z symdif Q')
1406
sage: X
1407
Z symdif Q
1408
"""
1409
return "Set-theoretic symmetric difference of %s and %s"%(self.__X,
1410
self.__Y)
1411
1412
def _latex_(self):
1413
r"""
1414
Return latex representation of self.
1415
1416
EXAMPLES::
1417
1418
sage: X = Set(ZZ).symmetric_difference(Set(QQ))
1419
sage: latex(X)
1420
\Bold{Z} \bigtriangleup \Bold{Q}
1421
"""
1422
return '%s \\bigtriangleup %s'%(latex(self.__X), latex(self.__Y))
1423
1424
def __iter__(self):
1425
"""
1426
Return iterator through elements of self.
1427
1428
Self is the formal symmetric difference of X and Y. This function is
1429
implemented by first iterating through the elements of X and
1430
yielding it if it is not in Y. Then it will iterate throw all
1431
the elements of Y and yielding it if it is not in X.
1432
1433
EXAMPLES::
1434
1435
sage: X = Set(ZZ).symmetric_difference(Primes())
1436
sage: I = X.__iter__()
1437
sage: I.next()
1438
0
1439
sage: I.next()
1440
1
1441
sage: I.next()
1442
-1
1443
sage: I.next()
1444
-2
1445
sage: I.next()
1446
-3
1447
"""
1448
for x in self.__X:
1449
if x not in self.__Y:
1450
yield x
1451
1452
for y in self.__Y:
1453
if y not in self.__X:
1454
yield y
1455
1456
1457
def __contains__(self, x):
1458
"""
1459
Return true if self contains x.
1460
1461
Since self is the formal symmetric difference of X and Y this function
1462
returns true if either X or Y (but now both) contains x.
1463
1464
EXAMPLES::
1465
1466
sage: X = Set(QQ).symmetric_difference(Primes())
1467
sage: 4 in X
1468
True
1469
sage: ComplexField().0 in X
1470
False
1471
sage: sqrt(2) in X # since sqrt(2) is currently symbolic
1472
False
1473
sage: sqrt(RR(2)) in X # since sqrt(RR(2)) is currently approximated
1474
True
1475
sage: pi in X
1476
False
1477
sage: 5/2 in X
1478
True
1479
sage: 3 in X
1480
False
1481
"""
1482
return (x in self.__X and x not in self.__Y) \
1483
or (x in self.__Y and x not in self.__X)
1484
1485
def cardinality(self):
1486
"""
1487
This tries to return the cardinality of this formal symmetric difference.
1488
1489
Note that this is not likely to work in very much generality,
1490
and may just hang if either set involved is infinite.
1491
1492
EXAMPLES::
1493
1494
sage: X = Set(GF(13)).symmetric_difference(Set(range(5)))
1495
sage: X.cardinality()
1496
8
1497
"""
1498
return len(list(self))
1499
1500