Вот моя проблема: у меня есть последовательность S (непустых, но возможно недифференцированных) множеств s_i, и для каждого s_i нужно знать, сколько множеств s_j в S (i ≠ j) являются подмножествами s_i.
Мне также нужна инкрементная производительность: как только у меня есть все мои счета, я могу заменить один набор s_i на некоторый поднабор s_i и обновить счеты постепенно.
Выполнение всего этого с использованием чисто функционального кода было бы огромным плюсом (код я в Scala).
Как установлено, включение является частичным упорядочением, я думал, что лучший способ решить мою проблему - построить DAG, который будет представлять диаграмму Хассе для наборов, с ребрами, представляющими включение, и соединить целочисленное значение с каждым node, представляющий размер суб-дага ниже node плюс 1. Тем не менее, я несколько дней пытаюсь разработать алгоритм, который строит диаграмму Хассе из частичного упорядочения (не говоря о инкрементальности!), даже хотя я думал, что это будет какой-то стандартный материал для студентов.
Вот моя структура данных:
case class HNode[A] (
val v: A,
val child: List[HNode[A]]) {
val rank = 1 + child.map(_.rank).sum
}
My 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 в DAG:
- найти все "корневые подмножества" rs_i из v в DAG, т.е. подмножества v, такие, что никакое надмножество rs_i не является подмножеством v. Это можно сделать довольно легко, выполнив поиск (BFS или DFS) на graph (
collect
функция, возможно, неоптимальная или даже некорректная). - создайте новый node n_v, дочерние элементы которого ранее были найдены rs_i.
- Теперь давайте узнаем, где нужно присоединить n_v: для данного списка корней найдите супермножества v. Если ни один не найден, добавьте n_v к корням и удалите подмножества n_v из корней. Else, выполните шаг 3 рекурсивно над дочерними элементами надстроек.
Я еще не полностью реализовал этот алгоритм, но он кажется нерегулярно цирконным и неоптимальным для моей, по-видимому, простой проблемы. Есть ли более простой алгоритм (Google не знал об этом)?