维护一组最小的子集

Question

以下是我想对以集合为元素的假设集合数据结构执行的操作：

1. 将一个集合插入到数据结构中，但是：(1) 如果新集合是任何现有集合的超集，则不要添加它 (2) 如果新集合是任何现有集合的子集，则删除它们。
2. 枚举当前集合中的所有集合

所有有问题的集合都是已知有限集合的子集，比如 {0..10^4}。

有没有办法有效地做到这一点？

Answer 1

这是关于此问题的最新论文：http://research.google.com/pubs/pub36974.html

简而言之，在最坏的情况下，你不可能比二次时间做得更好。但在实践中，有一些技巧可以加快速度。