Tạo một DAG từ một poset bằng cách sử dụng lập trình hàm stricly

Question

Đây là vấn đề của tôi: Tôi có một chuỗi S (nonempty nhưng có thể không phân biệt) bộ s_i, và cho mỗi s_i cần biết có bao nhiêu bộ s_j trong S (i ≠ j) là tập con của s_i.

Tôi cũng cần hiệu suất gia tăng: một khi tôi có tất cả số đếm, tôi có thể thay thế một bộ s_i bằng một số tập hợp con của s_i và cập nhật số lượng tăng dần.

Thực hiện tất cả điều này bằng cách sử dụng mã thuần túy sẽ là một điểm cộng lớn (tôi viết bằng Scala).

Khi đặt bao gồm là một phần, tôi nghĩ cách tốt nhất để giải quyết vấn đề của tôi là xây dựng một DAG đại diện cho sơ đồ Hasse của các bộ, với các cạnh đại diện, và nối giá trị nguyên cho mỗi nút đại diện cho kích thước của sub-dag bên dưới nút cộng 1. Tuy nhiên, tôi đã bị mắc kẹt trong vài ngày cố gắng phát triển thuật toán xây dựng sơ đồ Hasse từ thứ tự một phần (chúng ta không nói về sự gia tăng!), mặc dù tôi nghĩ nó sẽ là một số tài liệu đại học tiêu chuẩn.

Dưới đây là cấu trúc dữ liệu của tôi:

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

My DAG được xác định bởi một danh sách các rễ và một số đặt hàng phần:

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

Tôi khá mắc kẹt ở đây. Lần cuối cùng tôi đưa ra để thêm một giá trị mới v cho DAG là:

1. tìm tất cả "tập hợp con gốc" của v trong DAG, tức là tập con của v sao cho không có phần lớn của rs_i là tập con của v. Điều này có thể được thực hiện khá dễ dàng bằng cách thực hiện tìm kiếm (BFS hoặc DFS) trên biểu đồ (chức năng collect, có thể không tối ưu hoặc thậm chí thiếu sót).
2. tạo nút mới n_v, trẻ em trong số đó là rs_i được tìm thấy trước đây.
3. Bây giờ, chúng ta hãy tìm ra nơi n_v nên được đính kèm: cho một danh sách nhất định của rễ, tìm supersets của v.Nếu không tìm thấy, thêm n_v vào gốc và loại bỏ tập hợp con của n_v từ rễ. Khác, thực hiện bước 3 đệ quy trên trẻ em của supersets.

Tôi chưa triển khai đầy đủ thuật toán này, nhưng dường như nó không được xử lý triệt để và không tối ưu cho vấn đề đơn giản của tôi. Có một số thuật toán đơn giản có sẵn (Google đã không biết gì về điều này)?

Answer 1

Sau một số công việc, cuối cùng tôi đã giải quyết được vấn đề của mình, theo trực giác ban đầu của tôi. Phương pháp thu thập và đánh giá xếp hạng là thiếu sót, tôi viết lại chúng với đệ quy đuôi như một phần thưởng. Đây là mã tôi đắc:

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

tôi bây giờ phải kiểm tra một số tối ưu hóa: - cắt đứt chi nhánh với bộ hoàn toàn khác biệt khi thu thập các tập con (như Rex Kerr gợi ý) - xem nếu sắp xếp các bộ theo quy mô cải thiện quy trình (như mitchus được đề xuất)

Vấn đề sau đây là làm việc phức tạp (trường hợp xấu nhất) của hoạt động add() ra ngoài. Với n số bộ và kích cỡ của tập lớn nhất, độ phức tạp có thể là O (n²d), nhưng tôi hy vọng nó có thể được tinh chỉnh. Đây là lý do của tôi: nếu tất cả các bộ là khác biệt, DAG sẽ được giảm xuống một chuỗi các rễ/lá. Vì vậy, mỗi lần tôi cố gắng thêm một nút vào cấu trúc dữ liệu, tôi vẫn phải kiểm tra sự bao gồm với mỗi nút đã có (cả trong thu thập và đính kèm các thủ tục). Điều này dẫn đến kiểm tra bao gồm 1 + 2 +… + n = n (n + 1)/2 ∈ O (n²).

Mỗi phép thử bao gồm thiết lập là O (d), do đó là kết quả.

Answer 2

Giả DAG của bạn G chứa một nút v cho mỗi bộ, với các thuộc tính v.s (set) và v.count (số lượng các trường hợp của các thiết lập), bao gồm một nút G.root với G.root.s = union of all sets (nơi G.root.count=0 nếu thiết lập này không bao giờ xảy ra trong bộ sưu tập của bạn).

Sau đó, để đếm số lượng các tập con riêng biệt của s bạn có thể làm như sau (trong hỗn hợp bastardized của Scala, Python và pseudo-code):

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

nơi

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

Trong ý kiến ​​của tôi mặc dù, vì lý do hiệu suất bạn sẽ tốt hơn từ bỏ loại giải pháp hoàn toàn chức năng này ... nó hoạt động tốt trên danh sách và cây cối, nhưng hơn thế nữa sẽ trở nên khó khăn.