Thursday, March 10, 2016

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.

• 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();

for(int i = 0; i < size; ++i)
{
G group = result.get(i);

if (matcher.test(group, item))
{
}
}
}

return result;
}```

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

Thursday, March 10, 2016 11:31:48 AM UTC      Comments [0] -
Java | Tips and tricks
Archive
 < August 2024 >
SunMonTueWedThuFriSat
28293031123
45678910
11121314151617
18192021222324
25262728293031
1234567
Categories
 .NET AI Angular AngularJS Announce ASP.NET Azure BizTalk Server C++ Incremental Parser Java javascript JSF and Facelets kendoui ML.NET SCCBridge SQL Server puzzle Thinking aloud Tips and tricks Window Search xslt
Blogroll
Statistics
Total Posts: 387
This Year: 3
This Month: 0
This Week: 0