page387.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 121 行
HTML
121 行
<HTML>
<HEAD>
<TITLE>Sets, Multisets and Partitions</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html6705" HREF="page388.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page388.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html6703" HREF="book.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html6697" HREF="page386.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page386.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html6707" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html6708" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H1><A NAME="SECTION0013000000000000000000">Sets, Multisets and Partitions</A></H1>
<P>
<A NAME="chapsets"> </A>
<P>
In mathematics a <em>set</em><A NAME=28091> </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=28093> </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=12 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67116" SRC="img1586.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1586.gif" >, <IMG WIDTH=21 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67118" SRC="img1587.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1587.gif" >, <IMG WIDTH=65 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67120" SRC="img1588.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1588.gif" > and <IMG WIDTH=36 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67122" SRC="img1589.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1589.gif" > are all sets
the elements of which are drawn from <IMG WIDTH=114 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67124" SRC="img1590.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1590.gif" >.
The set of all possible elements, <I>U</I>, is called the
<em>universal set</em><A NAME=28095> </A>.
Note also that the elements comprising a given set are not ordered.
Thus, <IMG WIDTH=49 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67128" SRC="img1591.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1591.gif" > and <IMG WIDTH=49 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67130" SRC="img1592.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1592.gif" > are the same set.
<P>
There are many possible operations on sets.
In this chapter we consider the most common operations
for <em>combining sets</em>--union, intersection, difference:
<P>
<DL ><DT><STRONG>union</STRONG>
<DD>
The <em>union</em><A NAME=28099> </A>
(or <em>conjunction</em><A NAME=28101> </A>)
of sets <I>S</I> and <I>T</I>,
written <IMG WIDTH=39 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline67136" SRC="img1593.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1593.gif" >,
is the set comprised of all the elements of <I>S</I>
together with all the element 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=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline67136" SRC="img1593.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1593.gif" >.
If <IMG WIDTH=97 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67148" SRC="img1594.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1594.gif" > and <IMG WIDTH=70 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67150" SRC="img1595.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1595.gif" >, then <IMG WIDTH=141 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67152" SRC="img1596.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1596.gif" >.
<DT><STRONG>intersection</STRONG>
<DD>
The <em>intersection</em><A NAME=28103> </A>
(or <em>disjunction</em><A NAME=28105> </A>)
of sets <I>S</I> and <I>T</I>
is written <IMG WIDTH=39 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline67158" SRC="img1597.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1597.gif" >.
The elements of <IMG WIDTH=39 HEIGHT=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline67158" SRC="img1597.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1597.gif" > are those items
which are elements of <em>both</em> <I>S</I> and <I>T</I>.
If <IMG WIDTH=97 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67148" SRC="img1594.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1594.gif" > and <IMG WIDTH=70 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67150" SRC="img1595.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1595.gif" >, then <IMG WIDTH=82 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67170" SRC="img1598.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1598.gif" >.
<DT><STRONG>difference</STRONG>
<DD>
The <em>difference</em><A NAME=28108> </A>
(or <em>subtraction</em><A NAME=28110> </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>.
I.e., 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=97 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67148" SRC="img1594.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1594.gif" > and <IMG WIDTH=70 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67150" SRC="img1595.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1595.gif" >, then <IMG WIDTH=113 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67192" SRC="img1599.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1599.gif" >.
<P>
</DL>
<P>
Figure <A HREF="page387.html#figvenn" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page387.html#figvenn"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> illustrates the basic set operations using a
<em>Venn diagram</em><A NAME=28115> </A>.
A Venn diagram represents the membership of sets by regions of the plane.
In Figure <A HREF="page387.html#figvenn" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page387.html#figvenn"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> the two sets <I>S</I> and <I>T</I> divide the plane into the
four regions labeled <I>I</I>-<I>IV</I>.
The following table illustrates the basic set operations
by enumerating the regions that comprise each set.
<P>
<P><A NAME="28165"> </A><A NAME="figvenn"> </A> <IMG WIDTH=575 HEIGHT=200 ALIGN=BOTTOM ALT="figure28117" SRC="img1600.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1600.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="page387.html#figvenn" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page387.html#figvenn"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline67136" SRC="img1593.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1593.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=12 ALIGN=BOTTOM ALT="tex2html_wrap_inline67158" SRC="img1597.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1597.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="tex2html6709" HREF="page388.html#SECTION0013100000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page388.html#SECTION0013100000000000000000">Basics</A>
<LI> <A NAME="tex2html6710" HREF="page390.html#SECTION0013200000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page390.html#SECTION0013200000000000000000">Array and Bit-Vector Sets</A>
<LI> <A NAME="tex2html6711" HREF="page397.html#SECTION0013300000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page397.html#SECTION0013300000000000000000">Multisets</A>
<LI> <A NAME="tex2html6712" HREF="page404.html#SECTION0013400000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page404.html#SECTION0013400000000000000000">Partitions</A>
<LI> <A NAME="tex2html6713" HREF="page413.html#SECTION0013500000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page413.html#SECTION0013500000000000000000">Applications</A>
<LI> <A NAME="tex2html6714" HREF="page414.html#SECTION0013600000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page414.html#SECTION0013600000000000000000">Exercises</A>
<LI> <A NAME="tex2html6715" HREF="page415.html#SECTION0013700000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page415.html#SECTION0013700000000000000000">Projects</A>
</UL>
<HR><A NAME="tex2html6705" HREF="page388.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page388.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html6703" HREF="book.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html6697" HREF="page386.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page386.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html6707" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html6708" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?