📄 page399.html
字号:
<HTML><HEAD><TITLE>Union, Intersection, and Difference</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="tex2html5779" HREF="page400.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5777" HREF="page397.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5773" HREF="page398.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5781" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0012312000000000000000">Union, Intersection, and Difference</A></H3><P>Because multisets permit duplicates but sets do not,the definitions of union, intersection, and differenceare slightly modified for multisets.The <em>union</em><A NAME=27985> </A> of multisets <I>S</I> and <I>T</I>,written <IMG WIDTH=39 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline66511" SRC="img1541.gif" >,is the multiset comprised of all the elements of <I>S</I>together with all the element of <I>T</I>.Since a multiset may contain duplicates,it does not matter if the same element appears in <I>S</I> and <I>T</I>.<P>The subtle difference between union of sets and union of multisetsgives rise to an interesting and useful property.If <I>S</I> and <I>T</I> are regular sets,<P> <IMG WIDTH=369 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath66831" SRC="img1587.gif" ><P>On the other hand, if <I>S</I> and <I>T</I> are <em>multisets</em>,<P> <IMG WIDTH=315 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath66832" SRC="img1588.gif" ><P><P>The <em>intersection</em><A NAME=27988> </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 itemswhich are elements of <em>both</em> <I>S</I> and <I>T</I>.If a given element appears more than once in <I>S</I> or <I>T</I> (or both),the intersection contains <I>m</I> copies of that element,where <I>m</I> is the smaller of the number of times the element appearsin <I>S</I> or <I>T</I>.For example, if <IMG WIDTH=130 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66881" SRC="img1589.gif" > and <IMG WIDTH=101 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66883" SRC="img1590.gif" >,the intersection is <IMG WIDTH=114 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66885" SRC="img1591.gif" >.<P>The <em>difference</em><A NAME=27991> </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>.<P>Program <A HREF="page399.html#progmultisetAsArrayc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives theimplementations of the union, intersection, and difference methodsof <tt>MultisetAsArray</tt> class.This code is quite similar to that ofthe <tt>SetAsArray</tt> class (Program <A HREF="page391.html#progsetAsArrayc"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>)and the <tt>SetAsBitVector</tt> class (Program <A HREF="page394.html#progsetAsBitVectorb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).The worst-case running time of each of these operations is <I>O</I>(<I>N</I>).<P><P><A NAME="28245"> </A><A NAME="progmultisetAsArrayc"> </A> <IMG WIDTH=575 HEIGHT=543 ALIGN=BOTTOM ALT="program27999" SRC="img1592.gif" ><BR><STRONG>Program:</STRONG> <tt>MultisetAsArray</tt> class <tt>__or__</tt>, <tt>__and__</tt> and <tt>__sub__</tt> methods.<BR><P><P>Instead of using the Boolean operators<tt>and</tt>, <tt>or</tt>, and <tt>not</tt>,we have used <tt>+</tt> (integer addition),<tt>min</tt> and <tt>-</tt> (integer subtraction).The following table summarizes the operators used in the variousset and multiset implementations.<DIV ALIGN=CENTER><P ALIGN=CENTER><TABLE COLS=4 BORDER FRAME=HSIDES RULES=GROUPS><COL ALIGN=LEFT><COL ALIGN=CENTER><COL ALIGN=CENTER><COL ALIGN=CENTER><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP COLSPAN=3> class</TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP><P> operation </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>SetAsArray</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>SetAsBitVector</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>MultisetAsArray</tt> </TD></TR></TBODY><TBODY><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP>union </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>or</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>|</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>+</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> intersection </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>and</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>&</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>min</tt> </TD></TR><TR><TD VALIGN=BASELINE ALIGN=LEFT NOWRAP> difference </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>and</tt> and <tt>not</tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt>&</tt> and <tt></tt> </TD><TD VALIGN=BASELINE ALIGN=CENTER NOWRAP> <tt><=</tt> and <tt>-</tt> </TD></TR></TBODY></TABLE></P></DIV><HR><A NAME="tex2html5779" HREF="page400.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5777" HREF="page397.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5773" HREF="page398.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5781" 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 + -