472,378 Members | 1,648 Online

# Generics and Sets 11,448 Expert 8TB
Greetings,

Introduction

This week I'll write a bit about generics (those funny angular brackets). I need
an example and decided to use sets and some of their operations. This weeks'
article discusses one set class and two interesting operations on the set:
combinations and set partitioning. First a description of the algorithms is
given and then we'll have some fun with the generic implementation of them.

Combinations

For a given set S = [x, y, z] there are eight sets representing all possible
combinations of those three distinct elements:
• []
• [x]
• [y]
• [z]
• [x, y]
• [x, z]
• [y, z]
• [x, y, z]

Given that set S, how can we find all these combinations? Here's how: suppose
we can find all combinations of set S'= [y, z] which are: [], [y], [z] and [y, z]
Of course these subsets are combinations of the original set S as well, but
there's no 'x' to be found in them (of course not, because I left it out).

Simply add that element 'x' to all the subsets that make up the combinations
of set [y, z]; This is the result:

[x], [x, y], [x, z] and [x, y, z]

Together with the other four subsets we have constructed all eight combinations
of set S= [x, y, z]

But how did we find all combinations of set S'= [y, z]? We apply a similar
recursive reasoning here: suppose we can find all combinations of set S''= [z];
they are [] and [c]; they are part of all combinations of set S'= [y, z] and
we add element 'y' to it: [y], [y, z].

This may seem futile but here's how we find all combinations of set S''= [z]:
we find all combinations of the empty set, which is the empty set itself: [],
and we add element [z] to all the combinations (just one), which makes [z].

For a set with n elements there are 2^n combinations. This can easily be seen:
the empty set (zero elements) has one combination: the empty set itself. If
we add an element to the set we end up with twice the number of combinations:
the original combinations plus the original combinations with that new element
added to every combination. A set of one element has two combinations, a set of
two elements has four combinations etc. etc.

The recursive algorithm described above generates them all.

Partitions

A partition of a set S are one or more disjunct non-empty subsets and the union
of those sets form the set S again. For the set S= [x, y, z] the partitions are:
• [x, y, z]
• [x], [y, z]
• [x, y], [z]
• [x, z], [y]
• [x], [y], [z]

How do we find all partitions of a set? We apply a similar recursive reasoning:
suppose we can find all partitions of set S'= [y, z] which is:
• [y, z]
• [y], [z]

First we add the set [x] to every partition of set S':
• [x], [y, z]
• [x], [y], [z]

Next we add element 'x' to every set in the partitions of S', one by one:
• [x, y, z]
• [x, y], [z]
• [y], [x, z]

We end up with the same five partitions again. Try to find all partitions of
set S'= [y, z] given the partitions of set S''= [z]. The partitions of a single
element set is the single element set itself, so all partitions of set S'' is
the set S''= [z] itself.

By definition all partitions of an empty set is the empty set itself.

Sets

language has Set implementations available. I'm going to use the HashSet
implementation for the example in this article. I am going to change the behaviour
of the implementation a bit though: I want 'COW' sets. 'COW' is an acronym for
'Copy On Write'. COW implies that the set copies itself when it needs to be
altered; the copy is going to be altered instead. Let's get our hands dirty.
Here are the constructors of our (generic) set:

Expand|Select|Wrap|Line Numbers
1. public class S<T> extends HashSet<T> {
2.
3.     private static final long serialVersionUID = -8875179328198507416L;
4.
5.     public S(Collection<T> collection) { super(collection); }
6.
7.     public S(T arg) { this.add(arg); }
8.
9.     public S(T ... args) { super(Arrays.asList(args)); }
10.
11.     ...
12.
I added the serialVerionUID to keep Eclipse's mouth shut. This class has three
constructors: a form of a copy constructor taking a Collection<T> as its
argument; a constructor that takes a single element T as its argument and
a constructor that takes a (possibly empty) list of T arguements.

The last constructor allows us to write new S<T>() i.e. no elements at all
which results in the empty set.

I included the second constructor again to keep Eclipse's mouth shut. I need
sets of sets as in:

Expand|Select|Wrap|Line Numbers
1. S<S<T>> set= new S<S<T>>(new S<T>());
2.
Suppose I didn't include the second contructor then the Java compiler has to
deduce that given the last constructor a generic array of type S<T> needs to be
constructed to put that single argument in. A type S<T> is not a type T so
Eclipse warns about its own creativity. If I hadn't included that second
constructor everything would still be fine but I just don't like warnings.

The last constructor simply turns the varargs array to a List (which is a
collection too) so a superclass constructor can handle it all.

The Set interface defines 'add()' and 'addAll()' methods that return true or false
indicating whether or not the element(s) could be added. The same applies to the
'remove' and 'removeAll' methods. I don't want that behaviour, I want methods
that do the same but return the new set instead. Here goes:

Expand|Select|Wrap|Line Numbers
1.     private S<T> unionHere(T arg) {
2.
4.
5.         return this;
6.     }
7.
8.     public S<T> union(T arg) {
9.
10.         return new S<T>(this).unionHere(arg);
11.     }
12.
13.     public S<T> union(Collection<T> collection) {
14.
15.         S<T> copy= new S<T>(this);
16.
18.
19.         return copy;
20.     }
21.
22.     public S<T> difference(T arg) {
23.
24.         S<T> copy= new S<T>(this);
25.
26.         copy.remove(arg);
27.
28.         return copy;
29.     }
30.
31.     public S<T> difference(Collection<T> collection) {
32.
33.         S<T> copy= new S<T>(this);
34.
35.         copy.removeAll(collection);
36.
37.         return copy;
38.     }
39.
Note that I kept the first method private: I don't want the user to fiddle with
the set itself; if they want to do that they can fiddle with the superclass
methods that change the set itself.

The public methods above simply copy the set and apply the wanted operation on
the copy instead and return the copied set instead of returning a boolean value.

Note that all methods are generic: they don't care about what type T actually is.

So far so good, but I haven't done much yet. Here are the other set operations:
intersection, difference and symmetric difference. First a few examples of the
operations; A= [x, y, z], B=[y, z, t]
• intersection: [y, z]
• difference: [x]
• symmetric difference: [x, t]

The intersection of A and B are the elements that occur in both A and B. The
difference of A and B are those elements that occur in A but not in B. The
symmetric difference of A and B are those elements in A or B bot not in both.

The symmetric difference plus the intersection of two sets is the union of those
two sets. The symmetric difference of sets A and B is the union of the difference
of A and B and the difference of B and A.

Here's the source code:

Expand|Select|Wrap|Line Numbers
1.     public S<T> difference(Collection<T> collection) {
2.
3.         S<T> copy= new S<T>(this);
4.
5.         copy.removeAll(collection);
6.
7.         return copy;
8.     }
9.
10.     public S<T> symDifference(Collection<T> collection) {
11.
12.         return difference(collection).union(new S<T>(collection).difference(this));
13.     }
14.
15.     public S<T> intersection(Collection<T> collection) {
16.
17.         S<T> copy= new S<T>(this);
18.
19.         copy.retainAll(collection);
20.
21.         return copy;
22.     }
23.
There's not much more to tell about those methods than that they first make a
copy of the set and apply the operation on the copy of the set.

Combinations

The implementation of the 'combinations' method closely follows the description
in the paragraph above. The method returns a set of sets. The sets being the
individual combinations of the original set.

First the method constructs a set that contains the empty set. If the original
set isn't empty it walks over each element, removes it and generates all
combinations of the reduced set. It copies the combinations to a 'result' set
and copies them again after it had added that current element to the sets again.

Here's the code:

Expand|Select|Wrap|Line Numbers
1.     public S<S<T>> combinations() {
2.
3.         S<S<T>> result= new S<S<T>>(new S<T>());
4.
5.         for (T current : this) {
6.             S<S<T>> comb= difference(current).combinations();
8.             for (S<T> set : comb)
9.                 result.unionHere(set.union(current));
10.         }
11.
12.         return result;
13.     }
14.
It comes in quite handy that my methods return the modified set itself instead
of a true/false value. Not the generic type S<S<T>>, i.e. a set or sets of type T.

The method itself is defined in a generic definition of class S. The generic
type is T, so a (partial) specialization of S<S<T>> is valid too. In other
words: if, say, a definition of the union method for a type T is valid, then
automatically it is valid for a generic type S<T>. The above code makes use of
Java's generic behaviour.

I'm going to (ab)use that feature even more for the next algorithm implementation:

Partitions

This method uses the same implementation strategy: it recursively invokes itself
with a smaller set and uses the return value to collect the partitions of the
current set in an set of partitions. Here it is:

Expand|Select|Wrap|Line Numbers
1.     public S<S<S<T>>> partitions() {
2.
3.         S<S<S<T>>> result= new S<S<S<T>>>();
4.
5.         if (size() < 2)
6.             return result.unionHere(new S<S<T>>(this));
7.
8.         T current= iterator().next();
9.         S<S<S<T>>> part= difference(current).partitions();
10.
11.         for (S<S<T>> set : part) {
12.             result.unionHere(set.union(new S<T>(current)));
13.
14.             for (S<T> elem : set) {
15.                 S<S<T>> copy= set.difference(elem);
16.                 result.unionHere(copy.unionHere(elem.union(current)));
17.             }
18.         }
19.
20.         return result;
21.     }
22.
A partition is a set of sets, so all partitions together is a set of sets of
sets; the last sets contain elements of type T.

For sets containing at most one element a set containing a set that contains
that (almost) empty set is returned. Otherwise the reasoning as explained in
the paragraph above is applied and the filled 'result' set is returned.

As you can see, in a generic definition of a method for type <T> a type S<T>,
S<S<T>> and even S<S<S<T>>> are defined automatically because an S<T>, S<S<T>>
and an S<S<S<T>>> are pure generic types themselves as well.

This makes it possible to find intersections, combinations or whatever not just
for sets of, say, Strings, i.e. S<String> but also for sets of sets of Strings,
i.e. S<S<String>> or whatever elements in a set you want.

Examples

After all this programming I'd like to see some results; I tested the above
methods like this:

Expand|Select|Wrap|Line Numbers
1.     public static void main(String[] args) {
2.
3.         S<String> s= new S<String>("x", "y", "z");
4.         S<String> t= new S<String>("y", "z", "t");
5.
6.         System.out.println("union        : "+s.union(t));
7.         System.out.println("intersection : "+s.intersection(t));
8.         System.out.println("difference   : "+s.difference(t));
9.         System.out.println("symDifference: "+s.symDifference(t));
10.         System.out.println("combinations : "+s.combinations());
11.         System.out.println("partitions   : "+s.partitions());
12.     }
13.
And this was the (correct) output:

Expand|Select|Wrap|Line Numbers
1. union        : [t, z, y, x]
2. intersection : [z, y]
3. difference   : [x]
4. symDifference: [t, x]
5. combinations : [[], [z, x], [z, y], [z], [y], [z, y, x], [x], [y, x]]
6. partitions   : [[[z, x], [y]], [[z, y], [x]], [[z], [y], [x]], [[z, y, x]], [[z], [y, x]]]
7.
Concluding remarks

The chapter described a bit of set juggling and fiddling with the generics
feature of Java. I'm sure you'll have to read this little article a couple of
times to fully appreciate the generic feature and the recursive implementation
of both operations.

I hope to see you next week and,

kind regards,

Jos
Sep 17 '07 #1
1 6305 Shubhendu Sinha
1 Hi Jos

Thanks for your post. I wish to implement partitions() in c++ to find all partitions of a set. Can you suggest me the best way. If you could also send me the source of partitions algorithm, i could try to write that in c++.
Jun 27 '11 #2

 1 by: Helium | last post by: Is there any need for "System.Collections.Queue" any more? OK, .Net made the mistake to start without generics, but that is fixed now. Languages without support for generics could use... 27 by: Bernardo Heynemann | last post by: How can I use Generics? How can I use C# 2.0? I already have VS.NET 2003 Enterprise Edition and still can´t use generics... I´m trying to make a generic collection myCollection and... 23 by: Luc Vaillant | last post by: I need to initialise a typed parameter depending of its type in a generic class. I have tried to use the C++ template form as follow, but it doesn't work. It seems to be a limitation of generics... 12 by: Michael S | last post by: Why do people spend so much time writing complex generic types? for fun? to learn? for use? I think of generics like I do about operator overloading. Great to have as a language-feature, as... 9 by: sloan | last post by: I'm not the sharpest knife in the drawer, but not a dummy either. I'm looking for a good book which goes over Generics in great detail. and to have as a reference book on my shelf. Personal... 1 by: Vladimir Shiryaev | last post by: Hello! Exception handling in generics seems to be a bit inconsistent to me. Imagine, I have "MyOwnException" class derived from "ApplicationException". I also have two classes... 2 by: Joe | last post by: Hi I have a Generics List in a PropertyGrid I am able to Serialize it to XML but when I try to deserialize back to the class of the PropertyGrid The Constructor doesn't seem to fire to reload... 7 by: SpotNet | last post by: Hello NewsGroup, Reading up on Generics in the .NET Framework 2.0 using C# 2005 (SP1), I have a question on the application of Generics. Knowingly, Generic classes are contained in the... 13 by: rkausch | last post by: Hello everyone, I'm writing because I'm frustrated with the implementation of C#'s generics, and need a workaround. I come from a Java background, and am currently writing a portion of an... 2 by: Kemmylinns12 | last post by: Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and efficiency. While initially associated with cryptocurrencies... 0 by: WisdomUfot | last post by: It's an interesting question you've got about how Gmail hides the HTTP referrer when a link in an email is clicked. While I don't have the specific technical details, Gmail likely implements measures... 0 by: BLUEPANDA | last post by: At BluePanda Dev, we're passionate about building high-quality software and sharing our knowledge with the community. That's why we've created a SaaS starter kit that's not only easy to use but also... 0 by: Rahul1995seven | last post by: Introduction: In the realm of programming languages, Python has emerged as a powerhouse. With its simplicity, versatility, and robustness, Python has gained popularity among beginners and experts... 2 by: Ricardo de Mila | last post by: Dear people, good afternoon... I have a form in msAccess with lots of controls and a specific routine must be triggered if the mouse_down event happens in any control. Than I need to discover what... 1 by: Johno34 | last post by: I have this click event on my form. It speaks to a Datasheet Subform Private Sub Command260_Click() Dim r As DAO.Recordset Set r = Form_frmABCD.Form.RecordsetClone r.MoveFirst Do If... 1 by: ezappsrUS | last post by: Hi, I wonder if someone knows where I am going wrong below. I have a continuous form and two labels where only one would be visible depending on the checkbox being checked or not. Below is the... 0 by: jack2019x | last post by: hello, Is there code or static lib for hook swapchain present? I wanna hook dxgi swapchain present for dx11 and dx9. 0 by: DizelArs | last post by: Hi all) Faced with a problem, element.click() event doesn't work in Safari browser. Tried various tricks like emulating touch event through a function: let clickEvent = new Event('click', {...