I am the co-owner/developer of a software consulting and products company. I have been making a living off of Java since 2005 and during that time I've worked on large government projects, designed and build high-volume e-commerce platforms, and worked on a variety of business applications with dozens of technologies Carey is a DZone MVB and is not an employee of DZone and has posted 10 posts at DZone. You can read more from them at their website. View Full User Profile

Computing the Common and Unique Elements in Multiple Collections

03.20.2012
| 3793 views |
  • submit to reddit

This week, we’ll take a break from higher level problems and technology posts to deal with just a little code problem that a lot of us have probably faced. It’s nothing fancy or too hard, but it may save one of you 15 minutes someday, and occasionally it’s nice to get back to basics.

So let’s get down to it. On occasion, you’ll find you need to determine which elements in one collection exist in another, which are common, and/or which don’t exist in another collection. Apache Commons Collections has some some utility methods in CollectionUtils that are useful, notably intersection(), but this post goes a bit beyond that into calculating unique elements in collection of collections, and it’s always nice to get down to the details. We’ll also make the solution more generic by supporting any number of collections to operate against, rather than just two collections as CollectionUtils does. Plus there’s the fact that not all of us choose to or are able to include libraries just to get a couple useful utility methods.

When dealing with just two collections, it’s not a difficult problem, but not all developers are familiar with all the methods that java.util.Collection defines, so here is some sample code. They key is using the retainAll and removeAll methods together to build up the three sets – common, present in collection A only, and present in B only.

Set<String> a = new HashSet<String>();
a.add("a");
a.add("a2");
a.add("common");

Set<String> b = new HashSet<String>();
b.add("b");
b.add("b2");
b.add("common");

Set<String> inAOnly = new HashSet<String>(a);
inAOnly.removeAll(b);
System.out.println("A Only: " + inAOnly );

Set<String> inBOnly = new HashSet<String>(b);
inBOnly .removeAll(a);
System.out.println("B Only: " + inBOnly );

Set<String> common = new HashSet<String>(a);
common.retainAll(b);
System.out.println("Common: " + common);

Output:

A Only: [a, a2]
B Only: [b, b2]
Common: [common1]
Handling Three or More Collections

The problem is a bit more tricky when dealing with more than two collections, but it can be solved in a generic way fairly simply, as shown below:

Computing Common Elements
Computing common elements is easy, and this code will perform consistently even with a large number of collections.

public static void main(String[] args) {
   List<String> a = Arrays.asList("a", "b", "c");
   List<String> b = Arrays.asList("a", "b", "c", "d");
   List<String> c = Arrays.asList("d", "e", "f", "g");

   List<List<String>> lists = new ArrayList<List<String>>();
   lists.add(a);
   System.out.println("Common in A: " + getCommonElements(lists));

   lists.add(b);
   System.out.println("Common in A & B: " + getCommonElements(lists));

   lists.add(c);
   System.out.println("Common in A & B & C: " + getCommonElements(lists));

   lists.remove(a);
   System.out.println("Common in B & C: " + getCommonElements(lists));
}

public static <T> Set<T> getCommonElements(Collection<? extends Collection<T>> collections) {

    Set<T> common = new LinkedHashSet<T>();
    if (!collections.isEmpty()) {
       Iterator<? extends Collection<T>> iterator = collections.iterator();
       common.addAll(iterator.next());
       while (iterator.hasNext()) {
          common.retainAll(iterator.next());
       }
    }
    return common;
}

Output:

Common in A: [a, b, c]
Common in A & B: [a, b, c]
Common in A & B & C: []
Common in B & C: [d]

Computing Unique Elements
Computing unique elements is just about as straightforward as computing common elements. Note that this code’s performance will degrade as you add a large number of collections, though in most practical cases it won’t matter. I presume there are ways this could be optimized, but since I haven’t had the problem, I’ve not bothered tryin. As Knuth famously said, “We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil”.

public static void main(String[] args) {
   List<String> a = Arrays.asList("a", "b", "c");
   List<String> b = Arrays.asList("a", "b", "c", "d");
   List<String> c = Arrays.asList("d", "e", "f", "g");

   List<List<String>> lists = new ArrayList<List<String>>();
   lists.add(a);
   System.out.println("Unique in A: " + getUniqueElements(lists));

   lists.add(b);
   System.out.println("Unique in A & B: " + getUniqueElements(lists));

   lists.add(c);
   System.out.println("Unique in A & B & C: " + getUniqueElements(lists));

   lists.remove(a);
   System.out.println("Unique in B & C: " + getUniqueElements(lists));
}

public static <T> List<Set<T>> getUniqueElements(Collection<? extends Collection<T>> collections) {

    List<Set<T>> allUniqueSets = new ArrayList<Set<T>>();
    for (Collection<T> collection : collections) {
       Set<T> unique = new LinkedHashSet<T>(collection);
       allUniqueSets.add(unique);
       for (Collection<T> otherCollection : collections) {
          if (collection != otherCollection) {
             unique.removeAll(otherCollection);
          }
       }
   }

    return allUniqueSets;
}

Output:

Unique in A: [[a, b, c]]
Unique in A & B: [[], [d]]
Unique in A & B & C: [[], [], [e, f, g]]
Unique in B & C: [[a, b, c], [e, f, g]]

That’s all there is to it. Feel free to use this code for whatever you like, and if you have any improvements or additions to suggest, leave a comment. Developers all benefit when we share knowledge and experience.

Published at DZone with permission of Carey Flichel, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Daniel Krzywicki replied on Mon, 2012/04/02 - 1:22pm

Here is a version which will be much faster if there is many collections of few different items:

 

 

public static <T> List<Set<T>> getUniqueElements(final Collection<? extends Collection<T>> collections) {
	List<Collection<T>> orderedCollections = newArrayList(collections);
	List<Set<T>> uniqueSets = newArrayList();
	for (Collection<T> collection : orderedCollections) {
		uniqueSets.add(newLinkedHashSet(collection));
	}

	Set<T> leftToRightSum = newHashSet();
	Iterator<Set<T>> uniqueSetsLeftToRight = uniqueSets.iterator();
	for (Collection<T> collection : orderedCollections) {
		uniqueSetsLeftToRight.next().removeAll(leftToRightSum);
		leftToRightSum.addAll(collection);
	}

	Set<T> rightToLeftSum = newHashSet();
	Iterator<Set<T>> uniqueSetsRightToLeft = reverse(uniqueSets).iterator();
	for (Collection<T> collection : reverse(orderedCollections)) {
		uniqueSetsRightToLeft.next().removeAll(rightToLeftSum);
		rightToLeftSum.addAll(collection);
	}

	return uniqueSets;
}

 

 

 

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.