Генерировать DAG из поса
Вопрос
Вот моя проблема: у меня есть последовательность S (непустых, но, возможно, не отдельных) наборов S_i, и для каждого S_i нужно знать, сколько наборов S_J в s (i ≠ j) являются подмножествами s_i.
Мне также нужна инкрементная производительность: как только у меня есть все свои подсчеты, я могу заменить один набор S_i на некоторую подмножество S_I и обновить счетчик постепенно.
Выполнение всего этого с использованием чисто функционального кода было бы огромным плюсом (I код в Scala).
Поскольку установленное включение является частичным упорядочением, я подумал, что лучший способ решить мою проблему - создать DAG, который будет представлять диаграмму Hasse наборов, с ребрами, представляющими включение, и присоединиться к целочисленному значению к каждому узлу, представляющему размер Подпрограмма ниже узла плюс 1. Однако я застрял в течение нескольких дней, пытаясь разработать алгоритм, который создает диаграмму Hasse из частичного упорядочения (давайте не будем говорить о инкрементности!), Даже если я думал, что это будет некоторая часть Стандартный бакалавриат.
Вот моя структура данных:
case class HNode[A] (
val v: A,
val child: List[HNode[A]]) {
val rank = 1 + child.map(_.rank).sum
}
Мой даг определяется списком корней и некоторым частичным упорядочением:
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 of v в DAG, т. Е. Подмножества V, так что ни один из них не является подмножеством v. Это можно легко сделать, выполнив поиск (BFS или DFS) на графике (
collect
функция, возможно, не оптимальная или даже ошибочная). - Создайте новый узел N_V, дети которых являются ранее найденными RS_I.
- Теперь давайте выясним, где N_V должен быть прикреплен: для данного списка корней, узнайте суперсеты V. Если никто не найден, добавьте N_V в корни и удалите подмножества n_v из корней. Иначе выполните шаг 3 рекурсивно на детях Суперсет.
Я еще не внедрил этот алгоритм, но он кажется бессмысленно -циркулированным и не оптимальным для моей явно простой проблемы. Есть ли доступен какой -то более простой алгоритм (Google был невежественным по этому поводу)?
Решение
После некоторой работы я наконец -то закончил решить свою проблему после моей первоначальной интуиции. Метод сбора и оценка ранга были ошибочными, я переписал их с помощью хвостовой рекурсии в качестве бонуса. Вот код, который я получил:
final case class HNode[A](
val v: A,
val child: List[HNode[A]]) {
val rank: Int = 1 + count(child, Set.empty)
@tailrec
private def count(stack: List[HNode[A]], c: Set[HNode[A]]): Int =
if (stack == Nil) c.size
else {
val head :: rem = stack
if (c(head)) count(rem, c)
else count(head.child ::: rem, c + head)
}
}
// ...
private def add(v: A, roots: List[HNode[A]]): List[HNode[A]] = {
val newNode = HNode(v, collect(v, roots, Nil))
attach(newNode, roots)
}
private def attach(n: HNode[A], roots: List[HNode[A]]): List[HNode[A]] =
if (roots.contains(n)) roots
else {
val (supersets, remaining) = roots.partition { r =>
// Strict superset to avoid creating cycles in case of equal elements
po.tryCompare(n.v, r.v) == Some(-1)
}
if (supersets.isEmpty) n :: remaining.filter(r => !po.lteq(r.v, n.v))
else {
supersets.map(s => HNode(s.v, attach(n, s.child))) ::: remaining
}
}
@tailrec
private def collect(v: A, stack: List[HNode[A]], collected: List[HNode[A]]): List[HNode[A]] =
if (stack == Nil) collected
else {
val head :: tail = stack
if (collected.exists(c => po.lteq(head.v, c.v))) collect(v, tail, collected)
else if (po.lteq(head.v, v)) collect(v, tail, head :: (collected.filter(c => !po.lteq(c.v, head.v))))
else collect(v, head.child ::: tail, collected)
}
Теперь я должен проверить некоторую оптимизацию: - Отключить ветви с совершенно отдельными наборами при сборе подмножеств (как предложил Рекс Керр) - Посмотрите, улучшает ли сортировка наборов по размеру процесс (как предложил Митчус)
Следующая проблема состоит в том, чтобы выпустить (худший) сложность операции add (). С n количество наборов, и D размером с самый большой набор, сложность, вероятно, будет O (N²D), но я надеюсь, что она может быть уточнена. Вот мои рассуждения: если все наборы различны, DAG будет уменьшен до последовательности корней/листьев. Таким образом, каждый раз, когда я пытаюсь добавить узел в структуру данных, мне все равно приходится проверить включение с каждым уже присутствующим узлом (как в процедурах сбора, так и прикрепления). Это приводит к 1 + 2 +… + n = n (n + 1)/2 ∈ O (N²) проверки включения.
Каждый набор теста включения o (d), отсюда и результат.
Другие советы
Предположим, ваш даг G
содержит узел v
Для каждого набора, с атрибутами v.s
(набор) и v.count
(Количество экземпляров набора), включая узел G.root
с G.root.s = union of all sets
(куда G.root.count=0
Если этот набор никогда не происходит в вашей коллекции).
Затем подсчитать количество отдельных подмножеств s
Вы могли бы сделать следующее (в ублюдке смеси Scala, Python и Pseudo-Code):
sum(apply(lambda x: x.count, get_subsets(s, G.root)))
куда
get_subsets(s, v) :
if(v.s is not a subset of s, {},
union({v} :: apply(v.children, lambda x: get_subsets(s, x))))
По моему мнению, по причинам производительности вам было бы лучше отказаться от такого рода чисто функционального решения ... оно хорошо работает на списках и деревьях, но помимо этого становится тяжелым.