Вот моя проблема: у меня есть последовательность S из (непустых, но, возможно, не отличных) наборов s_i, и для каждого s_i нужно знать, сколько наборов s_j в S (i ≠ j) являются подмножествами s_i.
Мне также нужна дополнительная производительность: после того, как у меня будут все мои показатели, я могу заменить один набор s_i на некоторое подмножество s_i и постепенно обновлять значения.
Выполнение всего этого с использованием чисто функционального кода будетбыть огромным плюсом (я кодирую в Scala).
Поскольку включение множеств является частичным упорядочением, я подумал, что лучшим способом решения моей проблемы будет создание DAG, которая будет представлять диаграмму Хассе множеств,с ребрами, представляющими включение, и присоединяют целочисленное значение к каждому узлу, представляющему размер подэтапа ниже узла плюс 1. Однако я застрял на несколько дней, пытаясь разработать алгоритм, который строит диаграмму Хассе из частичного упорядочения(давайте не будем говорить о приросте!), хотя я думал, что это будет какой-то стандартный материал для студентов.
Вот моя структура данных:
case class HNode[A] (
val v: A,
val child: List[HNode[A]]) {
val rank = 1 + child.map(_.rank).sum
}
Мой DAG определяется спискомкорни и некоторые частичные упорядочения:
class Hasse[A](val po: PartialOrdering[A], val roots: List[HNode[A]]) {
def +(v: A): Hasse[A] = new Hasse[A](po, add(v, roots))
private def collect(v: A, roots: List[HNode[A]], collected: List[HNode[A]]): List[HNode[A]] =
if (roots == Nil) collected
else {
val (subsets, remaining) = roots.partition(r => po.lteq(r.v, v))
collect(v, remaining.map(_.child).flatten, subsets.filter(r => !collected.exists(c => po.lteq(r.v, c.v))) ::: collected)
}
}
Я застрял здесь.Последнее, что я пришел, чтобы добавить новое значение v в группу обеспечения доступности баз данных:
- найти все «корневые подмножества» rs_i для v в группе обеспечения доступности баз данных, т. Е. Подмножества v такие, что ни один из подмножеств rs_i не являетсяподмножество v. Это можно сделать довольно легко, выполнив поиск (BFS или DFS) на графике (функция
collect
, возможно, неоптимальная или даже ошибочная). - сборка нового узла n_v,потомки которого являются ранее найденными rs_i.
- Теперь давайте выясним, где должен быть прикреплен n_v: для заданного списка корней выясняем надмножества v. Если ничего не найдено, добавьте n_v к корнями удалить подмножества n_v из корней.Иначе, выполните шаг 3 рекурсивно на дочерних объектах суперсетей.
Я еще не полностью реализовал этот алгоритм, но он кажется излишне сложным и неоптимальным для моей, казалось бы, простой задачи.Есть ли какой-нибудь более простой алгоритм (Google не знал об этом)?