page403.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 89 行

HTML
89 行
字号 
<HTML><HEAD><TITLE>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="tex2html5821" HREF="page404.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5819" HREF="page386.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5813" HREF="page402.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html5823" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0012400000000000000000">Partitions</A></H1><A NAME="secsetspartitions">&#160;</A><P>Consider the finite universal set  <IMG WIDTH=149 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66651" SRC="img1553.gif"  >.A <em>partition</em><A NAME=28103>&#160;</A> of <I>U</I>is a finite set of sets  <IMG WIDTH=142 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66961" SRC="img1600.gif"  >with the following properties:<OL><LI>	The sets  <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59771" SRC="img447.gif"  >,  <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59801" SRC="img455.gif"  >, ...,  <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66967" SRC="img1601.gif"  > are pairwise <em>disjoint</em>.	That is,  <IMG WIDTH=76 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline66969" SRC="img1602.gif"  >	for all values of <I>i</I> and <I>j</I> such that  <IMG WIDTH=92 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66975" SRC="img1603.gif"  >.<LI>	The sets  <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59771" SRC="img447.gif"  >,  <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59801" SRC="img455.gif"  >, ...,  <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66967" SRC="img1601.gif"  > <em>span</em> the universe <I>U</I>.	That is,	<P> <IMG WIDTH=500 HEIGHT=65 ALIGN=BOTTOM ALT="eqnarray28107" SRC="img1604.gif"  ><P></OL><P>For example, consider the universe  <IMG WIDTH=87 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66985" SRC="img1605.gif"  >.There are exactly five partitions of <I>U</I>:<P> <IMG WIDTH=500 HEIGHT=120 ALIGN=BOTTOM ALT="eqnarray28112" SRC="img1606.gif"  ><P>In general, given a universe <I>U</I> of size <I>n</I><I>&gt;</I>0,i.e., |<I>U</I>|=<I>n</I>,there are  <IMG WIDTH=76 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline66995" SRC="img1607.gif"  > partitions of <I>U</I>,where  <IMG WIDTH=28 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline66999" SRC="img1608.gif"  > is the so-called<em>Stirling number of the second kind</em><A NAME=28126>&#160;</A>which denotes the number of ways to partition a set of <I>n</I> elementsinto <I>m</I> nonempty disjoint subsets.<A NAME="tex2html720" HREF="footnode.html#28256"><IMG  ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A><P>Applications which use partitions typicallystart with an initial partitionand refine that partition either by joining or by splittingelements of the partition according to some application-specific criterion.The result of such a computation is the partition obtainedwhen no more elements can be split or joined.<P>In this chapter we shall consider only applications that beginwith the initial partition of <I>U</I>in which each item in <I>U</I> is in a separate element of the partition.Thus, the initial partition consists of |<I>U</I>| sets,each of size one (like  <IMG WIDTH=17 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline67015" SRC="img1611.gif"  > above).Furthermore, we restrict the applications in that we only allowelements of a partition to be joined--we do not allow elements to split.<P>The two operations to be performed on partitions are:<DL ><DT><STRONG>find</STRONG><DD>	Given an item in the universe, say  <IMG WIDTH=37 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67017" SRC="img1612.gif"  >,	find the element of the partition that contains <I>i</I>.	That is, find  <IMG WIDTH=47 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67021" SRC="img1613.gif"  > such that  <IMG WIDTH=40 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67023" SRC="img1614.gif"  >.    <DT><STRONG>join</STRONG><DD>	Given two distinct elements of a partition <I>P</I>,	say  <IMG WIDTH=46 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67027" SRC="img1615.gif"  > and  <IMG WIDTH=47 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67021" SRC="img1613.gif"  > such that  <IMG WIDTH=33 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline61295" SRC="img797.gif"  >,	create a new partition <I>P</I>'	by removing the two elements  <IMG WIDTH=13 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline67035" SRC="img1616.gif"  > and  <IMG WIDTH=14 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67037" SRC="img1617.gif"  > from <I>P</I>	and replacing them with a single element  <IMG WIDTH=47 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67041" SRC="img1618.gif"  >.<P> </DL><P>For example, consider the partition <IMG WIDTH=255 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline67043" SRC="img1619.gif"  >.The result of the operation  <IMG WIDTH=46 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67045" SRC="img1620.gif"  > is the set  <IMG WIDTH=76 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline67047" SRC="img1621.gif"  >because 3 is a member of  <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59801" SRC="img455.gif"  >.Furthermore, when we <em>join</em> sets  <IMG WIDTH=14 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59771" SRC="img447.gif"  > and  <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline59803" SRC="img456.gif"  >,we get the partition  <IMG WIDTH=141 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline67057" SRC="img1622.gif"  >.<P><BR> <HR><UL> <LI> <A NAME="tex2html5824" HREF="page404.html#SECTION0012401000000000000000">Representing Partitions</A><LI> <A NAME="tex2html5825" HREF="page405.html#SECTION0012410000000000000000">Implementing a Partition using a Forest</A><LI> <A NAME="tex2html5826" HREF="page409.html#SECTION0012420000000000000000">Collapsing Find</A><LI> <A NAME="tex2html5827" HREF="page410.html#SECTION0012430000000000000000">Union by Size</A><LI> <A NAME="tex2html5828" HREF="page411.html#SECTION0012440000000000000000">Union by Height or Rank</A></UL><HR><A NAME="tex2html5821" HREF="page404.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5819" HREF="page386.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5813" HREF="page402.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A>  <A NAME="tex2html5823" 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 &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page403.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page403.html 源码文件，采用 HTML 编程语言编写，共 89 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?