Эффективный способ идентификации именованных наборов с общими элементами в Scala

Question

Учитывая карту [String, Set [String]], что является элегантным и эффективным способом в Scala для определения набора всех пар различных ключей, где соответствующие наборы имеют непустое пересечение?

Например зафиксировать карту, как

val input = Map (
    "a" -> Set("x", "z"), 
    "b" -> Set("f") 
    "c" -> Set("f", "z", "44") 
    "d" -> Set("99") 
) 

то требуемый выход

Set(
    ("a", "c"), 
    ("b", "c") 
) 

Эффективное в этом контексте означает, что лучше, чем O (N^2), где п равно сумме числа элементов в семействе множеств, заданных в качестве входных данных.

Answer 1

Вы не можете получить более пессимистичную сложность, чем O (n^2). Посмотрите на следующий пример:

Map(
    1 -> Set("a"), 
    2 -> Set("a"), 
    3 -> Set("a"), 
    ... 
    n -> Set("a") 
) 

В этом случае каждая пара множеств имеет непустое пересечение. Таким образом, размер вывода в этом случае равен O (n^2), поэтому вы не можете получить лучшую сложность.

Очевидно, это не значит, что вы не можете думать о лучшем алгоритме, чем просто грубой силе. Например, вы можете преобразовать это:

val input = Map (
    "a" -> Set("x", "z"), 
    "b" -> Set("f") 
    "c" -> Set("f", "z", "44") 
    "d" -> Set("99") 
) 

в этом:

val transformed = Map (
    "x" -> Set("a"), 
    "z" -> Set("a", "c"), 
    "f" -> Set("b", "c"), 
    "44" -> Set("c"), 
    "99" -> Set("d") 
) 

Вы можете сделать это в линейном времени. Для этого я бы использовал сборщики коллекции Scala или измененные коллекции, чтобы избежать дорогостоящих операций с неизменяемыми коллекциями.

Тогда вы можете просто взглянуть на каждый набор, являющийся значением в этой преобразованной карте, и для каждого из них создать все возможные пары его элементов. Это может занять O (n^2), но если в вашем выходе не будет много пар, это будет намного быстрее.