Generowanie DAG z posetu przy użyciu ściśle funkcjonalnego programowania

Question

Oto mój problem: Mam sekwencję S (niepustych, ale prawdopodobnie nie odrębnych) zestawów s_i, a dla każdego s_i trzeba wiedzieć, ile zestawów s_j w S (i ≠ j) są podzbiorami s_i.

Potrzebuję również przyrostowej wydajności: po uzyskaniu wszystkich danych mogę zastąpić jeden zestaw s_i przez pewien podzbiór s_i i aktualizować liczniki przyrostowo.

Wykonanie tego wszystkiego przy użyciu czysto funkcjonalnego kodu byłoby ogromnym plusem (koduję w Scali).

Jako że włączenie do zestawu jest częściowym porządkiem, pomyślałem, że najlepszym sposobem rozwiązania mojego problemu byłoby zbudowanie DAG, które reprezentowałoby diagram Hassego zestawów, z krawędziami reprezentującymi inkluzja i dołączanie wartości całkowitej do każdego węzła reprezentujący rozmiar subdag poniżej węzła plus 1. Jednak utknąłem przez kilka dni, próbując opracować algorytm, który buduje diagram Hassego z częściowego porządkowania (nie mówmy o inkrementalności!), mimo że myślałem to byłby jakiś standardowy materiał licencjacki.

Oto moja struktura danych:

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

My DAG jest zdefiniowany przez liście i korzenie jakiegoś częściowego zamawiającego:

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

jestem całkiem zatrzymany tutaj. Ostatnim wymyśliłem, aby dodać nową wartość V do DAG jest:

1. znaleźć wszystkie „podzbiory root” rs_i V w DAG, czyli podzbiory v takie, że nie rozszerzeniem rs_i jest podzbiorem v. Można to zrobić całkiem łatwo, wykonując wyszukiwanie (BFS lub DFS) na wykresie (funkcja collect, prawdopodobnie nieoptymalna lub nawet wadliwa).
2. zbuduj nowy węzeł n_v, którego potomkami są poprzednio znalezione rs_i.
3. Teraz znajdźmy, gdzie powinno być dołączone n_v: dla danej listy pierwiastków, dowiedz się, jakie są supersetne v. Jeśli nie ma żadnych, dodaj n_v do korzeni i usuń podzbiory n_v z korzeni. W przeciwnym razie wykonaj krok 3 rekursywnie na dzieciach nadzorów.

Jeszcze nie wdrożyłem w pełni tego algorytmu, ale wydaje mi się, że jest on niepotrzebnie przerywany i nieoptymalny dla mojego pozornie prostego problemu. Czy jest jakiś prosty algorytm (Google nie ma o tym pojęcia)?

Answer 1

Po pewnym wysiłku w końcu rozwiązałem swój problem, podążając za moją początkową intuicją. Metoda zbierania i ocena rankingu były błędne, przepisałem je rekurencją ogona jako premią. Oto kod uzyskałem:

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

I teraz musi sprawdzić kilka optymalizacji: - odcięte gałęzie z całkowicie odmiennych zestawów podczas zbierania podzbiorów (jak sugeruje Rex Kerr) - sprawdzić, czy sortowania zestawów według wielkości poprawia proces (zgodnie z sugestią Mitchusa)

Następujący problem polega na pracy (najgorszy przypadek) złożoności operacji add(). W przypadku liczby zestawów, a d wielkości największego zestawu, złożoność prawdopodobnie będzie równa O (n²d), ale mam nadzieję, że uda się ją udoskonalić. Oto moje rozumowanie: jeśli wszystkie zbiory są różne, DAG zostanie zredukowany do sekwencji korzeni/liści. Dlatego za każdym razem, gdy próbuję dodać węzeł do struktury danych, nadal muszę sprawdzić, czy dany węzeł jest już włączony (zarówno w procedurach zbierania, jak i dołączania). Prowadzi to do kontroli włączenia 1 + 2 + ... + n = n (n + 1)/2 ∈ O (n²).

Każdy zestaw testu włączenia to O (d), stąd wynik.

Answer 2

Załóżmy, że DAG G zawiera węzeł v dla każdego zestawu, z atrybutami v.s (zbiór) i v.count (liczba wystąpień zestawie), w tym węzła G.root z G.root.s = union of all sets (gdzie G.root.count=0 jeśli ten zestaw nigdy nie występuje w twoja kolekcja).

następnie policzyć liczbę różnych podzbiorów s może wykonać następujące (w bastardized mieszaniny Scala Python i pseudo-kod):

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

gdzie

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

W moim zdaniem jednak, ze względu na wydajność lepiej byłoby porzucić tego rodzaju czysto funkcjonalne rozwiązanie ... działa dobrze na listach i drzewach, ale poza tym dzieje się trudne.