Mastering Algorithms with Perl

Chapter 6. Sets

I don’t want to belong to any club thatwouldhavemeasamember.

—Groucho Marx

Is the Velociraptor a carnivore or an herbivore? Is Bhutan an African river or an Asian state? Is a seaplane a boat, a plane, or both? These are all statements about membership in a set: the set of carnivores, the set of states, the set of planes. Wherever you have elements belonging to groups, you have sets. A set is simply a collection of items, called members or elements of the set. The most common definition of set members is that they are unique and unordered. In other words, a member can be in a set only once, and the ordering of the members does not matter: any sets containing the same members are considered equal. (However, at the end of this chapter, we’ll meet a few strange sets for which this isn’t true.)

In this chapter, we’ll explore how you can manipulate sets with Perl. We’ll show how to implement sets in Perl using either hashes or bit vectors. In parallel, we’ll demonstrate relevant CPAN modules, showing how to use them for common set operations. Then we’ll cover sets of sets, power sets, and multivalued sets, which include fuzzy sets and bags (also known as multisets). Finally, we’ll summarize the speed and size requirements of each variant.

There is no built-in datatype in Perl for representing sets. We can emulate them quite naturally with hashes or bit vectors. Since there are no native sets in Perl, obviously there aren’t native set operations either. However, developing ...