Genera un DAG da un post usando una programmazione evidentemente funzionale

Question

Ecco il mio problema: ho una sequenza s di set (non vuoti ma non distinti) S_I, e per ogni S_I ho bisogno di sapere quanti set s_j in s (i ≠ j) sono sottoinsiemi di s_i.

Ho anche bisogno di prestazioni incrementali: una volta che ho tutti i miei conteggi, potrei sostituire un set S_I con un sottoinsieme di S_I e aggiornare i conteggi in modo incrementale.

L'esecuzione di tutto questo usando il codice puramente funzionale sarebbe un enorme vantaggio (codice I in Scala).

Dato che l'inclusione del set è un ordine parziale, ho pensato che il modo migliore per risolvere il mio problema sarebbe stato quello di costruire un DAG che rappresenterebbe il diagramma di Hasse degli insiemi, con i bordi che rappresentano l'inclusione e unire un valore intero per ciascun nodo che rappresenta le dimensioni delle dimensioni Il sotto-dag sotto il nodo più 1. Tuttavia, sono rimasto bloccato per diversi giorni cercando di sviluppare l'algoritmo che costruisce il diagramma di Hasse dall'ordinamento parziale (non parliamo di incrementalità!), Anche se ho pensato che sarebbe stato un po ' Materiale universitario standard.

Ecco la mia struttura dei dati:

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

Il mio DAG è definito da un elenco di radici e alcuni ordini parziali:

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

Sono abbastanza bloccato qui. L'ultimo sono arrivato per aggiungere un nuovo valore V al DAG è:

1. Trova tutti i "sottoinsiemi di root" rs_i di V nel DAG, cioè sottoinsiemi di V in modo tale che nessun superset di RS_i sia un sottoinsieme di V. Questo può essere fatto abbastanza facilmente eseguendo una ricerca (BFS o DFS) sul grafico (collect funzione, forse non ottimale o addirittura imperfetta).
2. Costruisci il nuovo nodo N_V, i cui figli sono precedentemente trovati RS_I.
3. Ora, scopriamo dove dovrebbe essere allegato N_V: per un determinato elenco di radici, scopri i superset di v. Se non viene trovato nessuno, aggiungi N_V alle radici e rimuovi i sottoinsiemi di N_V dalle radici. Altrimenti, esegui il passaggio 3 in modo ricorsivo sui bambini dei superset.

Non ho ancora implementato pienamente questo algoritmo, ma sembra unvoluto unità e non ottimale per il mio problema apparentemente semplice. C'è un algoritmo più semplice disponibile (Google era all'oscuro su questo)?

Answer 1

Dopo un po 'di lavoro, ho finalmente finito per risolvere il mio problema, seguendo la mia intuizione iniziale. Il metodo di raccolta e la valutazione dei ranghi sono stati imperfetti, li ho riscritto con la recursione della coda come bonus. Ecco il codice che ho ottenuto:

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

Ora devo controllare un po 'di ottimizzazione: - Taglia le filiali con set totalmente distinti quando raccolgo sottoinsiemi (come suggerito da Rex Kerr) - vedere se l'ordinamento dei set per dimensione migliora il processo (come suggerito Mitchus)

Il seguente problema è far funzionare la complessità (peggiore) dell'operazione ADD (). Con n il numero di insiemi e le dimensioni del set più grande, la complessità sarà probabilmente O (N²D), ma spero che possa essere perfezionata. Ecco il mio ragionamento: se tutti i set sono distinti, il DAG sarà ridotto a una sequenza di radici/foglie. Pertanto, ogni volta che provo ad aggiungere un nodo alla struttura dei dati, devo comunque verificare l'inclusione con ciascun nodo già presente (sia nelle procedure di raccolta che di allega). Questo porta a 1 + 2 +… + n = n (n + 1)/2 ∈ O (n²) controlli di inclusione.

Ogni test di inclusione del set è O (d), quindi il risultato.

Answer 2

Supponiamo che il tuo DAG G contiene un nodo v Per ogni set, con attributi v.s (il set) e v.count (il numero di istanze del set), incluso un nodo G.root insieme a G.root.s = union of all sets (dove G.root.count=0 Se questo set non si verifica mai nella tua raccolta).

Quindi per contare il numero di sottoinsiemi distinti di s Potresti fare quanto segue (in una miscela bastardata di Scala, Python e Pseudo-Code):

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

dove

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

Secondo me, però, per motivi di prestazioni, starai meglio abbandonare questo tipo di soluzione puramente funzionale ... funziona bene su elenchi e alberi, ma al di là di ciò il gioco si fa duro.