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

Partitions

 

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

  1. The sets tex2html_wrap_inline59533, tex2html_wrap_inline59537, ..., tex2html_wrap_inline66745 are pairwise disjoint. That is, tex2html_wrap_inline66747 for all values of i and j such that tex2html_wrap_inline66753.
  2. The sets tex2html_wrap_inline59533, tex2html_wrap_inline59537, ..., tex2html_wrap_inline66745 span the universe U. That is,

    eqnarray28058

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

eqnarray28063

In general, given a universe U of size n>0, i.e., |U|=n, there are tex2html_wrap_inline66773 partitions of U, where tex2html_wrap_inline66777 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_inline66793 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_inline66795, find the element of the partition that contains i. That is, find tex2html_wrap_inline66799 such that tex2html_wrap_inline66801.
Join
Given two distinct elements of a partition P, say tex2html_wrap_inline66805 and tex2html_wrap_inline66799 such that tex2html_wrap_inline61085, create a new partition P' by removing the two elements tex2html_wrap_inline66813 and tex2html_wrap_inline66815 from P and replacing them with a single element tex2html_wrap_inline66819.

For example, consider the partition tex2html_wrap_inline66821. The result of the operation tex2html_wrap_inline66823 is the set tex2html_wrap_inline66825 because 3 is a member of tex2html_wrap_inline59537. Furthermore, when we join sets tex2html_wrap_inline59533 and tex2html_wrap_inline59541, we get the partition tex2html_wrap_inline66835.




next up previous contents index

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