Как сгруппировать элементы из несортированной последовательности с помощью пользовательской логики?

Question

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

У меня есть несортированный список объектов:

myList = (A, Z, T, J, D, L, W...)

Этиобъекты имеют разные типы, но все имеют один и тот же родительский тип.

Некоторые объекты «соответствуют» друг другу с помощью пользовательской бизнес-логики:

A.matches(B) = True

A.matches(C) = False

(Правка: сопоставление коммутативное. X.matches(Y) = Y.matches(X))

Я ищу способ в Scala группировать те объекты, которые совпадают, поэтому я получаю что-то вроде:

myMatches = [ [A,B,C], [D,Z,X], [H], ...]

Вот подвох - соответствие не транзитивно .

A.matches(B) = True

B.matches(C) = True

A.matches(C) = False <---- A and C can only be associated through their matches to B

Я все еще хочу, чтобы [A,B,C] был сгруппирован, хотя A и C не совпадают напрямую.

Есть ли простой способ сгруппировать вместевсе вещи, которые соответствуют друг другу?Есть ли название для такой проблемы, чтобы я мог узнать об этом в Google?

Answer 1

Вот функциональное решение на основе Scala Set s.Предполагается, что несортированный список объектов не содержит дубликатов, и что все они наследуются от некоторого типа MatchT, который содержит соответствующий метод matches.

Это решение сначала группирует все объекты в наборы, которые содержат непосредственносоответствующие объекты.Затем он проверяет каждый набор по очереди и объединяет его с любыми другими наборами, которые имеют какие-либо общие элементы (непустое пересечение).

def groupByMatch[T <: MatchT](elems: Set[T]): Set[Set[T]] = {
  @tailrec
  def loop(sets: Set[Set[T]], res: Set[Set[T]]): Set[Set[T]] =
    sets.headOption match {
      case None =>
        res
      case Some(h) =>
        val (matches, noMatches) = res.partition(_.intersect(h).nonEmpty)
        val newMatches = h ++ matches.flatten

        loop(sets.tail, noMatches + newMatches)
    }

  val matchSets = objs.map(x => objs.filter(_.matches(x)) + x)

  loop(matchSets, Set.empty[Set[T]])
}

Здесь есть ряд недостатков, поэтому, если производительность является проблемойтогда нефункциональная версия, основанная на изменчивых Map s, скорее всего будет быстрее.

Answer 2

Согласно предположениям, что

• сопоставление является коммутативным, то есть, если A соответствует B, то B соответствует A
• , если A соответствует B, B соответствует C, а C соответствует Dвсе они должны быть в одной группе.

вам просто нужно выполнить поиск ( DFS или BFS ) по графику совпадений, начинающемуся с каждого элемента, которого еще нет в группе,Элементы, которые вы найдете в одной форме поиска ровно в одной группе.

Вот пример кода:

import scala.collection.mutable

case class Element(name: Char) {
  def matches(other: Element): Boolean = {
    val a = name - 'A'
    val b = other.name - 'A'
    a * 2 == b || b * 2 == a
  }

  override def toString: String = s"$name (${name - 'A'})"
}

def matchingGroups(elements: Seq[Element]): Seq[Seq[Element]] = {
  val notInGroup: mutable.Set[Element] = elements.to[mutable.Set]

  val groups: mutable.ArrayBuilder[Seq[Element]] = mutable.ArrayBuilder.make()
  val currentGroup: mutable.ArrayBuilder[Element] = mutable.ArrayBuilder.make()

  def fillCurrentGroup(element: Element): Unit = {
    notInGroup -= element
    currentGroup += element
    for (candidate <- notInGroup) {
      if (element matches candidate) {
        fillCurrentGroup(candidate)
      }
    }
  }

  while (notInGroup.nonEmpty) {
    currentGroup.clear()
    fillCurrentGroup(notInGroup.head)
    groups += currentGroup.result()
  }

  groups.result()
}

matchingGroups('A' to 'Z' map Element) foreach println

Здесь находятся следующие группы:

WrappedArray(M (12), G (6), D (3), Y (24))
WrappedArray(R (17))
WrappedArray(K (10), F (5), U (20))
WrappedArray(X (23))
WrappedArray(V (21))
WrappedArray(B (1), C (2), E (4), I (8), Q (16))
WrappedArray(H (7), O (14))
WrappedArray(L (11), W (22))
WrappedArray(N (13))
WrappedArray(J (9), S (18))
WrappedArray(A (0))
WrappedArray(Z (25))
WrappedArray(P (15))
WrappedArray(T (19))

Если matches отношение некоммутативно, эта проблема немного сложнее.В этом случае во время поиска вы можете столкнуться с несколькими различными группами, которые вы обнаружили во время предыдущих поисков, и вам придется объединить эти группы в одну.Может быть полезно представить группы с несвязанной структурой данных для более быстрого слияния.