📄 page386.html
字号:
<HTML><HEAD><TITLE>Sets, Multisets, and Partitions</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html5628" HREF="page387.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5626" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5620" HREF="page385.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5630" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0012000000000000000000">Sets, Multisets, and Partitions</A></H1><P><A NAME="chapsets"> </A><P>In mathematics a <em>set</em><A NAME=27530> </A> is a collection of elements,especially a collection having some feature or features in common.The set may have a finite number of elements,e.g., the set of prime numbers less than 100;or it may have an infinite number of elements,e.g., the set of right triangles.The <em>elements</em><A NAME=27532> </A> of a set may be anything at all--from simple integers to arbitrarily complex objects.However, all the elements of a set are distinct--a set may contain only one instance of a given element.<P>For example, <IMG WIDTH=14 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66491" SRC="img1534.gif" >, <IMG WIDTH=23 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66493" SRC="img1535.gif" >, <IMG WIDTH=66 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66495" SRC="img1536.gif" >, and <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66497" SRC="img1537.gif" > are all setsthe elements of which are drawn from <IMG WIDTH=114 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66499" SRC="img1538.gif" >.The set of all possible elements, <I>U</I>, is called the<em>universal set</em><A NAME=27534> </A>.Note also that the elements comprising a given set are not ordered.Thus, <IMG WIDTH=51 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66503" SRC="img1539.gif" > and <IMG WIDTH=50 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66505" SRC="img1540.gif" > are the same set.<P>There are many possible operations on sets.In this chapter we consider the most common operationsfor <em>combining sets</em>--union, intersection, difference:<P><DL ><DT><STRONG>union</STRONG><DD> The <em>union</em><A NAME=27538> </A> (or <em>conjunction</em><A NAME=27540> </A>) of sets <I>S</I> and <I>T</I>, written <IMG WIDTH=39 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline66511" SRC="img1541.gif" >, is the set comprised of all the elements of <I>S</I> together with all the elements of <I>T</I>. Since a set cannot contain duplicates, if the same item is an element of both <I>S</I> and <I>T</I>, only one instance of that item appears in <IMG WIDTH=39 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline66511" SRC="img1541.gif" >. If <IMG WIDTH=98 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66523" SRC="img1542.gif" > and <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66525" SRC="img1543.gif" >, then <IMG WIDTH=142 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66527" SRC="img1544.gif" >. <DT><STRONG>intersection</STRONG><DD> The <em>intersection</em><A NAME=27542> </A> (or <em>disjunction</em><A NAME=27544> </A>) of sets <I>S</I> and <I>T</I> is written <IMG WIDTH=39 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline66533" SRC="img1545.gif" >. The elements of <IMG WIDTH=39 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline66533" SRC="img1545.gif" > are those items which are elements of <em>both</em> <I>S</I> and <I>T</I>. If <IMG WIDTH=98 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66523" SRC="img1542.gif" > and <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66525" SRC="img1543.gif" >, then <IMG WIDTH=83 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66545" SRC="img1546.gif" >. <DT><STRONG>difference</STRONG><DD> The <em>difference</em><A NAME=27547> </A> (or <em>subtraction</em><A NAME=27549> </A>) of sets <I>S</I> and <I>T</I>, written <I>S</I>-<I>T</I>, contains those elements of <I>S</I> which are <em>not also</em> elements of <I>T</I>. That is, the result <I>S</I>-<I>T</I> is obtained by taking the set <I>S</I> and removing from it those elements which are also found in <I>T</I>. If <IMG WIDTH=98 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66523" SRC="img1542.gif" > and <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66525" SRC="img1543.gif" >, then <IMG WIDTH=114 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66567" SRC="img1547.gif" >.<P> </DL><P>Figure <A HREF="page386.html#figvenn"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates the basic set operations using a<em>Venn diagram</em><A NAME=27554> </A>.A Venn diagram represents the membership of sets by regions of the plane.In Figure <A HREF="page386.html#figvenn"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> the two sets <I>S</I> and <I>T</I> divide the plane into thefour regions labeled <I>I</I>-<I>IV</I>.The following table illustrates the basic set operationsby enumerating the regions that comprise each set.<P><P><A NAME="27604"> </A><A NAME="figvenn"> </A> <IMG WIDTH=575 HEIGHT=200 ALIGN=BOTTOM ALT="figure27556" SRC="img1548.gif" ><BR><STRONG>Figure:</STRONG> Venn diagram illustrating the basic set operations.<BR><P><P><DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=2 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=CENTER><COL ALIGN=LEFT><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> set </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> region(s) of Figure <A HREF="page386.html#figvenn"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A></TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP><I>U</I> </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>I</I>, <I>II</I>, <I>III</I>, <I>IV</I> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>S</I> </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>I</I>, <I>II</I> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>S</I>' </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>III</I>, <I>IV</I> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>T</I> </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>II</I>, <I>III</I> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=39 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline66511" SRC="img1541.gif" > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>I</I>, <I>II</I>, <I>III</I> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <IMG WIDTH=39 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline66533" SRC="img1545.gif" > </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>II</I> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>S</I>-<I>T</I> </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>I</I> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <I>T</I>-<I>S</I> </TD><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> <I>III</I> </TD></TR></TBODY></TABLE></P></DIV><BR> <HR><UL> <LI> <A NAME="tex2html5631" HREF="page387.html#SECTION0012100000000000000000">Basics</A><LI> <A NAME="tex2html5632" HREF="page389.html#SECTION0012200000000000000000">Array and Bit-Vector Sets</A><LI> <A NAME="tex2html5633" HREF="page396.html#SECTION0012300000000000000000">Multisets</A><LI> <A NAME="tex2html5634" HREF="page403.html#SECTION0012400000000000000000">Partitions</A><LI> <A NAME="tex2html5635" HREF="page412.html#SECTION0012500000000000000000">Applications</A><LI> <A NAME="tex2html5636" HREF="page413.html#SECTION0012600000000000000000">Exercises</A><LI> <A NAME="tex2html5637" HREF="page414.html#SECTION0012700000000000000000">Projects</A></UL><HR><A NAME="tex2html5628" HREF="page387.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5626" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5620" HREF="page385.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5630" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -