Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Partitions

 

Consider the finite universal set tex2html_wrap_inline67278. A partition  of U is a finite set of sets tex2html_wrap_inline67580 with the following properties:

  1. The sets tex2html_wrap_inline60305, tex2html_wrap_inline60309, ..., tex2html_wrap_inline67586 are pairwise disjoint. I.e.,

    displaymath67572

  2. The sets tex2html_wrap_inline60305, tex2html_wrap_inline60309, ..., tex2html_wrap_inline67586 span the universe U. I.e.,

    eqnarray28630

For example, consider the universe tex2html_wrap_inline67596. There are exactly five partitions of U:

eqnarray28635

In general, given a universe U of size n>0, i.e., |U|=n, there are tex2html_wrap_inline67606 partitions of U, where tex2html_wrap_inline67610 is the so-called Stirling number of the second kind  which denotes the number of ways to partition a set of n elements into m nonempty disjoint subsets.gif

Applications which use partitions typically start with an initial partition and refine that partition either by joining or by splitting elements of the partition according to some application-specific criterion. The result of such a computation is the partition obtained when no more elements can be split or joined.

In this chapter we shall consider only applications that begin with the initial partition of U in which each item in U is in a separate element of the partition. Thus, the initial partition consists of |U| sets, each of size one (like tex2html_wrap_inline67626 above). Furthermore, we restrict the applications in that we only allow elements of a partition to be joined--we do not allow elements to split.

The two operations to be performed on partitions are:

Find
Given an item in the universe, say tex2html_wrap_inline67628, find the element of the partition that contains i. I.e., find tex2html_wrap_inline67632 such that tex2html_wrap_inline67634.
Join
Given two distinct elements of a partition P, say tex2html_wrap_inline67638 and tex2html_wrap_inline67632 such that tex2html_wrap_inline61938, create a new partition P' by removing the two elements tex2html_wrap_inline67646 and tex2html_wrap_inline67648 from P and replacing them with a single element tex2html_wrap_inline67652.

For example, consider the partition tex2html_wrap_inline67654. The result of the operation tex2html_wrap_inline67656 is the set tex2html_wrap_inline67658 because 3 is a member of tex2html_wrap_inline60309. Furthermore, when we join sets tex2html_wrap_inline60305 and tex2html_wrap_inline60313, we get the partition tex2html_wrap_inline67668.




next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.