Générer un DAG à partir d'un poset en utilisant la programmation fonctionnelle stricly

Question

Voici mon problème: j'ai une séquence S (mais peut-être pas non vide distincts) ensembles S_I, et pour chaque besoin S_I de savoir combien de jeux s_j en S (i ? j) sont des sous-ensembles de S_I.

Je dois aussi la performance supplémentaire: une fois que j'ai tous mes comptes, je remplacer un ensemble S_I par un sous-ensemble de S_I et mettre à jour les comptes progressivement

.

Effectuer tout cela en utilisant le code purement fonctionnel serait un énorme plus (code I Scala).

Comme l'inclusion ensemble est un ordre partiel, je pensais que la meilleure façon de résoudre mon problème serait de construire un DAG qui représenterait le diagramme de Hasse des ensembles, avec des arêtes représentant l'inclusion, et se joindre à une valeur entière à chaque noeud représentant la taille du sous-dag en dessous du nœud plus 1. Cependant, j'ai été coincé pendant plusieurs jours à essayer de développer l'algorithme qui construit le diagramme de Hasse de l'ordre partiel (ne parlons pas au sujet incrémentalité!), même si je pensais que ce serait un certain matériel de premier cycle standard.

Voici ma structure de données:

case class HNode[A] (
  val v: A,
  val child: List[HNode[A]]) {
  val rank = 1 + child.map(_.rank).sum
}

Mon DAG est défini par une liste des racines et une commande partielle:

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)
    }
}

Je suis assez coincé ici. La dernière je suis venu d'ajouter une nouvelle valeur v au DAG est:

1. trouver tous les « sous-ensembles de racines » de rs_i de v dans le DAG, par exemple, des sous-ensembles de v tels qu'aucun surensemble de rs_i est un sous-ensemble de v. Cela peut se faire assez facilement en effectuant une recherche (BFS ou DFS) sur la graphique (fonction collect, peut-être non-optimale ou même imparfaite).
2. construire le nouveau nœud N_V, les enfants qui sont les rs_i précédemment trouvés.
3. Maintenant, nous allons savoir où N_V doit être attaché. Pour une liste donnée de racines, savoir surensembles de v Si aucun ne trouve, ajoutez N_V aux racines et supprimer des sous-ensembles de N_V à partir des racines. Sinon, passez à l'étape 3 récursive sur les enfants des Surensembles.

Je n'ai pas encore pleinement mis en œuvre cet algorithme, mais il semble uncessarily circonvoluted et pour mon problème non optimal apparemment simple. Y at-il un algorithme plus simple disponible (sur ce Google était complètement paumé)?

Answer 1

Après quelques travaux, j'ai finalement fini par résoudre mon problème, suite à mon intuition initiale. La méthode et l'évaluation Collect rang étaient viciées, je les réécris avec la queue-récursion comme un bonus. Voici le code I obtenu:

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)
    }

Je dois maintenant vérifier une optimisation: - couper des branches avec des ensembles totalement distinctes lors de la collecte des sous-ensembles (comme suggéré Rex Kerr) - si le tri des lots en taille permet d'améliorer le processus (comme suggéré mitchus)

Le problème suivant est de travailler le (pire des cas) la complexité de l'opération hors de add (). Avec n le nombre de jeux, et d la taille du plus grand ensemble, la complexité sera probablement O (n²d), mais je l'espère peut être affiné. Voici mon raisonnement: si tous les ensembles sont distincts, la DAG sera réduite à une séquence de racines / feuilles. Ainsi, chaque fois que je tente d'ajouter un nœud à la structure de données, je dois encore vérifier l'inclusion à chaque noeud déjà présent (à la fois dans collect et procédures joindre). Cela conduit à 1 + 2 + ... + n = n (n + 1) / 2 ? O (n²) les contrôles d'inclusion.

Chaque jeu test d'inclusion est O (d), d'où le résultat.

Answer 2

Supposons que votre DAG G contient un nœud v pour chaque jeu, avec des attributs v.s (l'ensemble) et v.count (le nombre d'instances de l'ensemble), y compris un G.root de nœud avec G.root.s = union of all sets (où G.root.count=0 si cet ensemble ne se produit jamais dans votre collection).

Ensuite, pour compter le nombre de sous-ensembles distincts de s, vous pouvez effectuer les opérations suivantes (dans un mélange bâtarde de Scala, Python et pseudo-code):

sum(apply(lambda x: x.count, get_subsets(s, G.root)))

où

get_subsets(s, v) :
   if(v.s is not a subset of s, {}, 
      union({v} :: apply(v.children, lambda x: get_subsets(s, x))))

A mon avis cependant, pour des raisons de performance que vous serait mieux abandonner ce genre de solution purement fonctionnelle ... il fonctionne bien sur les listes et les arbres, mais au-delà les choses se corsent.