有效计算部分有序集合上的最小元素

Question

我有一个集合列表，我想根据子集关系将其排序为部分顺序。

事实上，我不需要完整的排序，只需要最少的元素。

如果我没有记错的话，每个最小元素应该定义相应图的一个单独的组件 - 并且这个组件应该是一个满足半格。

解决这个问题最方便的空间和时间效率的方法是什么？也许有一种方法不需要构建整个图？也许有一种已知的算法，其术语比我上面天真地描述的更好？

我知道上面未指定时间和空间要求，但我很高兴收到任何建议，无论它们是否被证明是最佳的......

背景:我目前正在构建一个完整的图形数据库，其中包含集合之间的所有边，然后查找没有泛化的节点，但这非常复杂、缓慢并且需要大量（磁盘）空间。上述列表包含 约1亿套.

Answer 1

一种方法是通过增加大小来对集合进行排序，然后重复执行以下操作：拍摄列表中的第一个设置，输出它，并从列表中删除所有占空比。这将输出所有最小集合。运行时间是 $ o（nk）$ 设置比较plus $ o（n \ log n）$ 排序的步骤，其中 $ n $ 是您拥有的集合数和 $ k $ 是数字最小的元素。或者，要另一种方式，如果每个设置包含 $ m $ 元素，则运行时间将大约 $ o（ n（k + \ log n）m）$ 基本步骤。

为什么按大小排序？这是一个优化。最小的集合是最小的（列表中没有较小的基数，所以它的子集没有任何一部分可以在列表中），因此尺寸是识别必须肯定最小的集合的有用技巧。

不按大小排序，最坏情况的运行时间可能最终成为 $ o（n ^ 2）$ 设置比较（或 $ O（n ^ 2 m）$ 基本步骤），当 $ k \ ll n $ 时，更糟糕的是。

---

这是该算法的优化版本。让 $ m $ 是存储一组集合的数据结构，如trie：例如，set $ \ {1,3,6,7 \} $ 对应于 $ 1367 $ ，并相应地存储在TRIE中。最初， $ m $ 为空。重复以下内容：从列表中拍摄下一个set $ s $ ;检查是否在 $ m $ 中是一个 $ s $ 的子集;如果没有，请插入 $ s $ 进入 $ m $ ;最后从列表中删除 $ s $ （或向列表中的下一个元素提升指针）。 “检查...”操作可以使用Trie的递归遍历相当有效地进行。最后，一旦你经历了整个列表，输出 $ m $ 。

优化算法的最坏情况运行时间保持不变。在实践中，运行时间可能会显着提高，也许像<跨度类=“math-container”> $ o（nm）$ 基本步骤在某些情况下，如果您是幸运的话（但不计算在上面）。您可以尝试两者，并在练习上练习您正在处理的那种工作负载。

Answer 2

我找到了解决方案 本文第 12 页.

作为证明提到的算法应转换为以下 python 代码：

T = set([]);
for x in X:
    rem = set([]);
    spe = False;
    for a in T:
        rel = oracle(x,a);
        if rel == "x>a":
            spe = True;
            break;
        elif rel == "x<a":
            rem.add(a);
    if not spe:
        T -= rem;
        T.add(x);

我期望 break 对于实际运行时间至关重要，因此排序可能是个好主意 X 提前休息是为了早点休息——但我对此并不确定。

我在这里看到的另一点是 > 应该是非自反的，所以 x>x 不成立。但对于这段代码来说，如果这样做的话会更好。如果 a==x, ，它会打破而不是不必要地进一步寻找。

更新： 我现在已经能够在 Python 中测试不同的实现。请允许我直接给出 python 代码，我认为它与伪代码非常相似——也许对很多人来说更具体。

以下是摘自论文的实现：

def oracle(rep1,rep2):
    if generalizes(rep2,rep1):
        return ">";
    elif generalizes(rep1,rep2):
        return "<";
    return None;

def find_min_els_(repIDs,ID2rep):
    min_els = set([]);
    for x in repIDs:
        spec_of_x = set([]);
        x_is_spec = False;
        for min_el in min_els:
            relation = oracle(ID2rep[x],ID2rep[min_el]);
            if relation == ">":
                x_is_spec = True;
                break;
            elif relation == "<":
                spec_of_x.add(min_el);
        if not x_is_spec:
            min_els -= spec_of_x;
            min_els.add(x);
    return min_els;

现在事实证明这太慢了，我们已经可以从复杂性中看出，如果偏序的宽度（即数字）是非常糟糕的 m 最小元素的数量预计会很大。

诀窍是使该算法独立于 m 通过避免遍历所有当前的最小元素。相反，我们可以利用结果集中的查找速度很快的事实（我猜这就是 trie 发挥作用的地方）。

对于每个 x，我们生成所有概括。现在复杂性取决于 x 的数量及其大小，但不太取决于最小元素的数量（只有 O(n log n)？）。更好的是，由于我们现在必须从初始元素列表中删除非最小元素而不是添加它们，因此每个 x 所用的时间在运行时会减少而不是增加。

这是相应的代码：

def generalizations(spe_rep,gens):
    for el in spe_rep:
        gen_rep = spe_rep - set([el]);
        gen_str = string(gen_rep);
        if not gen_str in gens:
            gens.add(gen_str);
            yield gen_str;
            for x in generalizations(gen_rep,gens):
                yield x;

def find_min_els(repIDs,ID2rep):
    min_els = set(repIDs);
    for x in repIDs:
        for genID in generalizations(ID2rep[x],set([])):
            if genID in min_els:
                min_els.remove(x);
                break;
    return min_els;

这使用了生成器函数 generalizations() 以避免计算更多的概括 x 一旦在当前的最小元素中已经找到了一个。对于我的数据来说，这已经相当快了，但也许可以通过首先生成更通用的泛化来改进（如果这使它更快，则需要进行测试），特别是仅生成由已观察到的元素组成的泛化在当前的最小元素中。例如如果我们的 x 是 {a,b,c}, ，但当前没有最小元素 c 在其中，我们不必生成任何子集 x 其中包含 c, ， IE。仅有的 {a,b},{a},{b},{}.