Java algorithm to "multiply" two lists of lists ((A),(B))*((C,C),(D,D))==((A,C,C),(A,D,D),(B,C,C),(B,D,D))

Question

I have two lists of lists, the sublists represent paths. I want to find all paths.

List<List<E>> pathList1
List<List<E>> pathList2

The naive solution of course:

List<List<E>> result = new ArrayList<List<E>>();

for(List<E> p1 : pathList1) {
   for(List<E> p2: pathList2) {
      List<E> newList = new ArrayList<E>(p1.size()+p2.size());
      newList.addAll(p1);
      newList.addAll(p2);
      result.add(newList);
   }
}

Unrelated theoretical question

I've recently learned about time complexity. So this is a self check, I hope someone can comment if I am correct.

Let N = num lists in pathList1

Let M = num lists in pathList2

Let X = average length of path in pathList1

Let Y = average length of path in pathList2

So if asked "What is the complexity of this function?" I would give

~O(NM(X + Y))

I was wondering if there was a faster way to do this?

Maybe a better data structure?

Do it concurrently?

Make some sort of "future" of sorts and return that instead? (Full disclosure, I'm 97% ignorant on futures).

I'm open to clever tricks and unique solutions, or purely practical.

Thanks.

Answer 1

I'm confused by what your goal is exactly.

If you have the following lists of paths "(A,B,C)(D,E)" and "(C,D)(A,B)"

then your current code would return

"(A,B,C,C,D),(D,E,C,D),(A,B,C,A,B),(D,E,A,B)"

Is that what you want? That's not all paths, that's all combinations of paths.

A list of all paths would be

"(A,B,C)(D,E)(C,D)(A,B)"

Which could be performed in simple O(N) time.

Also with Big-O notation we usually aren't concerned about the individual variables, only the overall scale of the problem complexity. It is generally written purely as a function of a single variable, n, which is the number of elements.

But if you want to "multiply" the two lists, each element of one against the other, then its going to be O(n^2) and there's not really any faster way.

Answer 2

You can take a look at guava in particular to the Sets#cartesianProduct

i.e. you can do something of this sort:

Sets.cartesianProduct(ImmutableList.of(
       ImmutableSet.of(Sets.newHashSet(pathList1)),
       ImmutableSet.of(Sets.newHashSet(pathList2)))