Алгоритм Java для "умножения" двух списков списков ((A),(B))*((C,C),(D,D))==((A,C,C),(A,D,D),(В, С, С), (В,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);
   }
}

Несвязанный теоретический вопрос

Я недавно узнал о сложности времени. Так что это самопроверка, я надеюсь, что кто-то может прокомментировать, если я прав.

Пусть N = num списков в pathList1

Пусть M = num списков в pathList2

Пусть X = средняя длина пути в pathList1

Пусть Y = средняя длина пути в pathList2

Так что если спросить "Какова сложность этой функции?" Я бы дал

~O(NM(X + Y))

Мне было интересно, есть ли более быстрый способ сделать это?

Может быть, лучшая структура данных?

Делать это одновременно?

Сделать что-то вроде "будущего" и вернуть его вместо этого? (Полное раскрытие, я на 97% не осведомлен о фьючерсах).

Я открыт для умных трюков и уникальных решений, или чисто практических.

Благодарю.

Answer 1

Вы можете взглянуть на гуаву, в частности на наборы #cartesianProduct

то есть вы можете сделать что-то вроде этого:

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

Answer 2

Я смущен тем, что ваша цель точно.

Если у вас есть следующие списки путей "(A,B,C)(D,E)" и "(C, D) (A, B)"

тогда ваш текущий код вернется

"(А, В, С, С, D), (D, Е, С, D), (А, В, С, А, В), (D, Е, А, В)"

Это то, что вы хотите? Это не все пути, это все комбинации путей.

Список всех путей будет

"(А, В, С) (D, Е) (С, D) (А, В)"

Который мог быть выполнен за простое O(N) время.

Кроме того, с помощью нотации Big-O нас обычно не беспокоят отдельные переменные, а только общий масштаб сложности проблемы. Обычно он написан исключительно как функция единственной переменной n, которая является числом элементов.

Но если вы хотите "умножить" два списка, каждый элемент одного на другой, тогда это будет O(n^2), и на самом деле нет более быстрого пути.