Группировка ключей на основе значений в карте scala

Question

Предположим, у меня такая карта скала -

Map[String, List[String]] = Map(
"A"->List(1,2,3),
"B"->List(2,4),
"C"->List(4,5),
"D"->List(7,8,9),
"E"->List(8,9),
"F"->List(4,5,7),
"G"->List(1,3,2)
)

Я хочу сгруппировать ключи так, чтобы их пересечение не было пустым. Например, результат должен быть как -

Map(
List("A","B","G")->List(2),
List("C","F")->List(4,5),
List("D","E")->List(8,9)
)

Обратите внимание, что может быть несколько выходов, например, может быть Список ("B", "C") -> Список (4). Мне просто нужно выбрать кого-нибудь, пока присутствуют все ключи И ключи не должны повторяться, например, «B» и «C» уже присутствуют на карте, так что позже, даже если мы все еще нашли пару для пересечения, не пустой, например, мы нашли «B» и «C», мы НЕ должны добавлять его. Мой способ решения этой проблемы включает преобразование списка значений в набор, а затем итерацию по всем элементам карты таким образом, чтобы он продолжал пересекать свое значение со следующим значением, и если пересечение не пустое, мы сгруппируем ключи.

Но я хочу знать, есть ли другой способ сделать это.

РЕДАКТИРОВАТЬ -

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

Answer 1

Я превратил значения карты в List[Int], чтобы упростить загрузку в IDE.Это можно легко отменить.

val m :Map[String, List[Int]] = Map(
  "A"->List(1,2,3),
  "B"->List(2,4),
  "C"->List(4,5),
  "D"->List(7,8,9),
  "E"->List(8,9),
  "F"->List(4,5,7),
  "G"->List(1,3,2))

Затем я fold на клавишах, чтобы увидеть, какие из них intersect.

m.keys.foldLeft(List.empty[(List[String],List[Int])]){case (acc,k) =>
  val (not, has) = acc.partition(_._2.intersect(m(k)).isEmpty)
  has.headOption.fold((List(k),m(k)) :: acc){case (s,v) =>
    (k::s, v.intersect(m(k))) :: has.tail ::: not
  }
}.toMap
//res0: Map[List[String],List[Int]] = Map(List(D, E) -> List(8, 9)
//                                       ,List(C, F) -> List(4, 5)
//                                       ,List(B, G, A) -> List(2))

Это немного "грубая сила" подходполучение пересечения один раз для partition() и еще раз при построении новой записи в аккумуляторе, и исходная Карта m разыменовывается несколько раз для каждого значения k.

---

объяснение

Из ключей карты я строю List из (List[String],List[Int]) кортежей.Для каждого ключа карты накопленный список разбивается между теми элементами, где есть пересечение со значением нового ключа (has), и теми, где пересечение отсутствует (not).

Я хватаюсьтолько 1-й элемент из группы has.Если его нет, этот ключ и его значение добавляются к результату, в противном случае ключ добавляется к списку ключей has.head, и список значений корректируется с учетом текущего пересечения.Этот новый элемент добавляется к has.tail (пересечения игнорируются) и объединяется со всем в списке not.

Answer 2

Вы можете следовать этому подходу для получения желаемого результата.

Допустим, у вас есть ввод в следующем формате.

val map1: Map[String, List[Int]] = Map(
  "A"->List(1,2,3),
  "B"->List(2,4),
  "C"->List(4,5),
  "D"->List(7,8,9),
  "E"->List(8,9),
  "F"->List(4,5,7)
)

Чтобы получить уникальные значения, мы конвертируем Список значений в набор, чтобы получить пересечение между значениями

val map2 = map1.map(x => (x._1,x._2.toSet))

    val result: Map[List[String], Set[Int]] = 
for(a <- map2;
    b <- map2 if( (a._1!=b._1)   && (a._2 intersect b._2).nonEmpty))
yield( List(a._1,b._1) -> (a._2 intersect b._2) )

Эта функция выдаст вам результат как

result: Map[List[String],Set[Int]] = Map(List(D, F) -> Set(7), List(C, F) -> Set(4, 5), List(E, D) -> Set(8, 9), List(B, C) -> Set(4), List(B, A) -> Set(2), List(A, B) -> Set(2), List(F, C) -> Set(4, 5), List(C, B) -> Set(4), List(D, E) -> Set(8, 9), List(F, D) -> Set(7), List(F, B) -> Set(4), List(B, F) -> Set(4))

Пожалуйста, дайте мне знать, если у вас есть какие-либо вопросы относительно этого подхода. Спасибо