Java: how to partition a collection into equivalence classes?

Question

I have a list(!) of items:

• A
• B
• C
• D
• E
• ...

and I want to group them:

• [A, C, D]
• [B, E]
• ...

Groups are defined by:

• all items in the group are equal according to a custom function f(a, b) -> boolean
• f(a, b) = f(b, a)

Question: is there ready API to do so?

<T> List<List<T>> group(Collection<T> collection, BiFunction<T, T, Boolean> eqF);

UPDATE. This question is totally not for a scenario when you can define some quality to group by! In this case Java 8 Collectors.groupingBy is the simplest answer.

I am working with multidimensional vectors and equality function looks like:

• metrics(a, b) < threshold

For this case defining a hash is equal to solving the initial task :)

Answer 1

Your scenario sounds like a good use case for the groupingBy collector. Normally, instead of supplying an equality function, you supply a function that extracts a qualifier. The elements are then mapped to these qualifiers in lists.

i.e.

Map<Qualifier, List<T>> map = list.stream()
    .collect(Collectors.groupingBy(T::getQualifier));

Collection<List<T>> result = map.values();

In the case the identity of T is your qualifier, you could use Function.identity() as an argument.

But this becomes a problem when your qualifier is more than 1 field of T. You could use a tuple type, to create an alternate identity for T but this only goes so far, as there needs to be a separate tuple class for each number of fields.

---

If you want to use groupingBy you really need to create a temperate alternate identity for T, so you don't have to change T's equals and hashCode methods.

To create a proper identity, you need to implement equals and hashCode (or always return 0 for a hash code, with performance downsides). There is no API class for this, that I know of, but I have made a simple implementation:

interface AlternateIdentity<T> {    
    public static <T> Function<T, AlternateIdentity<T>> mapper(
            BiPredicate<? super T, Object> equality, ToIntFunction<? super T> hasher) {
        return t -> new AlternateIdentity<T>() {
            @Override
            public boolean equals(Object other) {
                return equality.test(t, other);
            }

            @Override
            public int hashCode() {
                return hasher.applyAsInt(t);
            }
        };
    }
}

Which you could use like:

Collection<List<T>> result
    = list.stream()
        .collect(Collectors.groupingBy(
            AlternateIdentity.mapper(eqF, hashF)
        ))
        .values();

Where eqF is your function, and hashF is a hash code function that hashes the same fields as eqF tests. (Again, you could also just return 0 in hashF, but having a proper implementation would speed things up.)

Answer 2

You can use hashing to do this in linear time.

To do this, you need to first implement the hashCode() function in your object, so it returns an equal hash value for equal elements (for example by XOR-ing the hash codes of its instance properties). Then you can use a hash table of sets to group your elements.

Map<Integer, Set<T>> hashMap = new HashMap<>();
for (T element : collection) {
    if (!hashMap.containsKey(element.hashCode())
         hashMap.put(element.hashCode(), new HashSet<T>());
    hashMap.get(element.hashCode()).add(element);
}

As equal elements produce the same hash, they will be inserted into the same equivalence class.

Now, you can obtain a collection of all equivalence classes (as sets) by using hashMap.values();

Answer 3

I'm pretty sure there's nothing in the standard API for this. You might try a third-party collection class, like Trove's TCustomHashSet. (It's interesting that, according to a comment in this related thread, the Guava group has (for now) rejected a similar class. See the discussion here.)

The alternative is to roll your own solution. If you don't have too many items, I'd suggest a brute-force approach: keep a list of item lists and, for each new item, go through the list of lists and see if it is equal to the first element of the list. If so, add the new item to the matching list and, if not, add a new list to the list of lists with that item as the only member. The computation complexity is not very good, which is why I would only recommend this where the number of items is small or execution time performance is not an issue at all.

A second approach is to modify your item class to implement the custom equality function. But to use that with the hash-based collection classes, you'll need to override hashcode() as well. (If you don't use a hash-based collection, you might as well go with the brute force approach.) If you don't want to (or can't) modify the item class (e.g., you want to use various equality tests), I'd suggest creating a wrapper class that can be parameterized with the equality (and hash code) strategy to use. (This is kind of half way between modifying your item class and using the Trove class.)

Answer 4

Here's a simple example grouping strings. You'll need to supply a different function other than identity() if your objects you want to group are more complex.

public class StreamGroupingBy
{

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

      Map<String,List<String>> result = items.stream().collect(
              Collectors.groupingBy( Function.identity() ) );
      System.out.println( result );
   }
}

Output:

{a=[a, a, a, a], b=[b, b, b], c=[c, c], d=[d], x=[x]}

Answer 5

I would also recommend to implement a hashing mechanism. You can do something similar with Guava FluentIterable:

FluentIterable.from(collection)
    .index(new Function<T, K>() {
        K apply(T input) {
            //transform T to K hash
        }
    })//that would return ImmutableListMultimap<K, T>
    .asMap()//that would return Map<K, Collection<T>>
    .values();//Collection<Collection<T>>