📄 page412.html
字号:
<HTML><HEAD><TITLE>Applications</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="tex2html5922" HREF="page413.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5920" HREF="page386.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5914" HREF="page411.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5924" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0012500000000000000000">Applications</A></H1><P>One of the most important applications of partitionsinvolves the processing of equivalence relations.Equivalence relations arise in many interesting contexts.For example, two nodes in an electric circuit are electrically equivalentif there is a conducting path (a wire) connecting the two nodes.In effect, the wires establish an electrical equivalence relation overthe nodes of a circuit.<P>A similar relation arises among the classes in a Python program.Consider the following Python code fragment:<PRE>class A(object): passclass B(A): passclass C(A): passclass D(B): passclass E(C): pass</PRE>The classes <tt>A</tt>, <tt>B</tt>, <tt>C</tt>, <tt>D</tt> and <tt>E</tt>are equivalent in the sense that they are all subclasses of the class <tt>A</tt>.(By definition, a class is a subsclass of itself.)In effect, the class declarations establish anequivalence relation over the classes in a Python program.<P><BLOCKQUOTE> <b>Definition (Equivalence Relation)</b><A NAME="defnsetsequivalence"> </A>An <em>equivalence relation</em><A NAME=29525> </A><A NAME=29526> </A>over a universal set <I>U</I> is a relation <IMG WIDTH=11 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline67245" SRC="img1654.gif" >with the following properties:<OL><LI> The relation <IMG WIDTH=11 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline67245" SRC="img1654.gif" > is <em>reflexive</em><A NAME=29529> </A>. That is, for every <IMG WIDTH=41 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67249" SRC="img1655.gif" >, <IMG WIDTH=39 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline67251" SRC="img1656.gif" >.<LI> The relation <IMG WIDTH=11 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline67245" SRC="img1654.gif" > is <em>symmetric</em><A NAME=29531> </A>. That is, for every pair <IMG WIDTH=41 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67249" SRC="img1655.gif" > and <IMG WIDTH=40 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67257" SRC="img1657.gif" >, if <IMG WIDTH=38 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline67259" SRC="img1658.gif" > then <IMG WIDTH=39 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline67261" SRC="img1659.gif" >.<LI> The relation <IMG WIDTH=11 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline67245" SRC="img1654.gif" > is <em>transitive</em><A NAME=29533> </A>. That is, for every triple <IMG WIDTH=41 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67249" SRC="img1655.gif" >, <IMG WIDTH=40 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67257" SRC="img1657.gif" > and <IMG WIDTH=39 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67269" SRC="img1660.gif" >, if <IMG WIDTH=38 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline67259" SRC="img1658.gif" > and <IMG WIDTH=38 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline67273" SRC="img1661.gif" > then <IMG WIDTH=38 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline67275" SRC="img1662.gif" >.</OL></BLOCKQUOTE><P>An important characteristic of an equivalence relation is that itpartitions the elements of the universal set <I>U</I> intoa set of <em>equivalence classes</em><A NAME=29537> </A>.That is, <I>U</I> is partitioned into <IMG WIDTH=142 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66961" SRC="img1600.gif" >,such that for every pair <IMG WIDTH=41 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67249" SRC="img1655.gif" > and <IMG WIDTH=40 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67257" SRC="img1657.gif" >, <IMG WIDTH=38 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline67259" SRC="img1658.gif" > if and only if<I>x</I> and <I>y</I> are in the same element of the partition.That is, <IMG WIDTH=38 HEIGHT=17 ALIGN=MIDDLE ALT="tex2html_wrap_inline67259" SRC="img1658.gif" > if there exists a value of <I>i</I>such that <IMG WIDTH=103 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline67297" SRC="img1663.gif" >.<P>For example, consider the universe <IMG WIDTH=114 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67299" SRC="img1664.gif" >.and the equivalence relation <IMG WIDTH=11 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline67245" SRC="img1654.gif" > defined over <I>U</I> defines as follows:<P><A NAME="eqnsetsequiv"> </A> <IMG WIDTH=559 HEIGHT=39 ALIGN=BOTTOM ALT="multline29538" SRC="img1665.gif" ><P>This relation results in the following partition of <I>U</I>:<P> <IMG WIDTH=364 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath67239" SRC="img1666.gif" ><P><P>The list of equivalences in Equation <A HREF="page412.html#eqnsetsequiv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> contains many redundancies.Since we know that the relation <IMG WIDTH=11 HEIGHT=8 ALIGN=BOTTOM ALT="tex2html_wrap_inline67245" SRC="img1654.gif" >is reflexive, symmetric and transitive,it is possible to infer the complete relation from the following list<P> <IMG WIDTH=380 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath67240" SRC="img1667.gif" ><P>The problem of finding the set of equivalence classesfrom a list of equivalence pairs is easily solved using a partition.Program <A HREF="page412.html#progalgorithmsb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows how it can be doneusing the <tt>PartitionAsForest</tt> class defined in Section <A HREF="page405.html#secsetspforest"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="29548"> </A><A NAME="progalgorithmsb"> </A> <IMG WIDTH=575 HEIGHT=336 ALIGN=BOTTOM ALT="program29545" SRC="img1668.gif" ><BR><STRONG>Program:</STRONG> Application of disjoint sets--finding equivalence classes.<BR><P><P>The algorithm first gets a positive integer <tt>n</tt> from the inputand creates a partition, <tt>p</tt>,of the universe <IMG WIDTH=138 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67309" SRC="img1669.gif" > (lines 4-5).As explained in Section <A HREF="page405.html#secsetspforest"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the initial partition comprises <tt>n</tt> disjoint sets of size one.That is, each element of the universal setis in a separate element of the partition.<P>Each iteration of the main loop processes one equivalence pair (lines 6-15).An equivalence pair consists of two numbers, <tt>i</tt> and <tt>j</tt>,such that <IMG WIDTH=39 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67311" SRC="img1670.gif" > and <IMG WIDTH=39 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67313" SRC="img1671.gif" >.The <em>find</em> operation is used to determine the sets <tt>s</tt> and <tt>t</tt>in partition <tt>p</tt> that contain elements <tt>i</tt> and <tt>j</tt>,respectively (lines 10-11).<P>If <tt>s</tt> and <tt>t</tt> are not the same set,then the disjoint sets are unitedusing the <em>join</em> operation (lines 12-13).Otherwise, <tt>i</tt> and <tt>j</tt> are already in the same setand the equivalence pair is redundant (line 15).After all the pairs have been processed,the final partition is printed (line 16).<P><HR><A NAME="tex2html5922" HREF="page413.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5920" HREF="page386.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5914" HREF="page411.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5924" 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 + -