Common and Unique Elements In Multiple Collections

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.

Reference: Computing Common and Unique Elements In Multiple Collections – Java & from our JCG partner Craig Flichel at the Carfey Software Blog blog.

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

JPA Mini Book

Learn how to leverage the power of JPA in order to create robust and flexible Java applications. With this Mini Book, you will get introduced to JPA and smoothly transition to more advanced concepts.

JVM Troubleshooting Guide

The Java virtual machine is really the foundation of any Java EE platform. Learn how to master it with this advanced guide!

Given email address is already subscribed, thank you!
Oops. Something went wrong. Please try again later.
Please provide a valid email address.
Thank you, your sign-up request was successful! Please check your e-mail inbox.
Please complete the CAPTCHA.
Please fill in the required fields.

Leave a Reply


three − = 1



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy | Contact
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.
Do you want to know how to develop your skillset and become a ...
Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

Get ready to Rock!
You can download the complementary eBooks using the links below:
Close