Java算法到 "multiply"两个列表列表((A),(B))*((C,C),(D,D))==((A,C,C),(A,D,D), (B,C,C),(B,D,D))

Question

我有两个列表列表，子列表代表路径。我想找到所有路径。

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

当然是天真的解决方案:

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

不相关的理论问题

我最近了解了时间复杂度。所以这是一个 self 检查，我希望有人能评论我是否正确。

让 N = num lists in pathList1

设 M = pathList2 中的 num 个列表

令 X = pathList1 中路径的平均长度

令 Y = pathList2 中路径的平均长度

所以如果问“这个函数的复杂度是多少？”我愿意给

~O(NM(X + Y))

我想知道是否有更快的方法来做到这一点？

也许是更好的数据结构？

同时进行？

创造某种“ future ”并返回它？ (完全披露，我 97% 对 future 一无所知)。

我乐于接受巧妙的技巧和独特的解决方案，或者纯粹实用的解决方案。

谢谢。

Answer 1

可以看看guava 特别是 Sets#cartesianProduct

即你可以做这样的事情:

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