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.

i think your method takes same time as to print the result which is optimal so i think you cannot improve on the bound — Vikram Bhat, Jan 08 '14 at 18:46

score 3 · Answer 1 · answered Jan 08 '14 at 19:03

3

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)))

answered Jan 08 '14 at 19:03

Алексей

1,847
12
15

Do you think it would be faster this way? I'm looking for speed, not ease of use. But I'll definitely check out the library, thanks! – user498001 Jan 08 '14 at 19:26
1

@user498001 during all my interaction with this library, it proofed to be very robust (though i have not used that method in particular) – Алексей Jan 08 '14 at 20:09
@user498001 `The Guava project contains several of Google's core libraries` I hope for the sake of the internet that it's fast! – Marc-Andre Jan 09 '14 at 14:00

score 0 · Answer 2 · answered Jan 08 '14 at 18:50

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.

I apologize, by all combinations I meant each path from list one and each path from list two. — user498001, Jan 08 '14 at 19:24
That's still confusing. Did you read my post? So, are you saying you did just want one list of the paths in one and two, or are you saying you want to combine each with each? Be clear! — SpacePrez, Jan 08 '14 at 21:34

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))

2 Answers2