Our recent task required us to find all sets of not intersecting rectangles for a rectangle list.

At first glance it did not look like a trivial task. Just consider that for a list of N rectangles you can form 2^N different subsets. So, even result list, theoretically, can be enormous.

Fortunately, we knew that our result will be manageable in size. But nevertheless, suppose you have a list of couple of hundred rectangles, how would you enumerate all different sets of rectangles?

By the way, this task sounds the same as one of a Google interview's question. So, you may try to solve it by yourself before to check our solution.

We didn't even dare to think of brute-force solution: to enumerate all sets and then check each one whether it fits our needs.

Instead we used induction:

• Suppose S(N) - is an solution for our task for N rectangles R(n), where S(N) is a set of sets of rectangles;
• Then solution for S(N+1) will contain whole S(N), R(N+1) - a set consisting of single rectangle, and some sets of rectangles from S(N) combinded with R(N+1) provided they fit the condition;
• S(0) - is an empty set.

The algorithm was implemented in java, and at first it was using Streaming and recursion.

Then we have figured out that we can use Stream.reduce or Stream.collect to implement the same algorithm. That second implementation was a little bit longer but probably faster, and besides it used standard idioms.

But then at last step we reformulated the algorithms in terms of Collections.

Though the final implementation is the least similar to original induction algorithm, it's straightforward and definitely fastest among all implementations we tried.

So, here is the code:

/**
 * For a sequence of items builds a list of matching groups.
 * @param identity an identity instance used for the group.
 * @param items original sequence of items.
 * @param matcher a group matcher of item against a group.
 * @param combiner creates a new group from a group (optional) and an item.
 * @return a list of matching groups.
 */
public static <T, G> List<G> matchingGroups(
  G identity,
  Iterable<T> items, 
  BiPredicate<G, T> matcher,
  BiFunction<G, T, G> combiner)
{
  ArrayList<G> result = new ArrayList<>();
  
  for(T item: items)
  {
    int size = result.size();
    
    result.add(combiner.apply(identity, item));
   
    for(int i = 0; i < size; ++i)
    {
      G group = result.get(i);
      
      if (matcher.test(group, item))
      {
        result.add(combiner.apply(group, item));
      }
    }
  }
    
  return result;
}

The sample project on GitHub contains implementation and a tests of this algorithm.