java - 找到幂集和集合列表的交集

Question

给定一个大的任意集合 S 和一个集合列表 S_n，找到 S_n 中作为 S 子集的所有集合。

换句话说，PowerSet(S) 和 S_n 的交集。

是否有任何 Java 库可以快速完成这种数学运算？集合 S_n 的列表相对较小，最多几百个，而这些集合最多包含 10 个项目。但是，任意集合（在运行时确定）可能有多达 20 个项目（在 1000 个集合中），因此具有巨大的幂集。

我正在寻找一种方法，也许是进行某种类型的离线计算，以非常快速地（50 毫秒或更短）进行这种确定。

示例：S = { 1, 2, 3 }

S_n = [ { 1 }, { 1, 2 }, { 5, 4, 6 } ]

结果 = [ { 1 }, { 1, 2 } ]

score 1 · Accepted Answer

伪代码

for each subset s_n
    if (s.containsAll(s_n)) {
        add it to the result list
    }

score 1 · Accepted Answer

1

我认为您可以使用retainAll(Collection<?> c) 接口中声明的标准方法java.util.Set

于 2012-10-02T16:26:54.540 回答

score 0 · Accepted Answer

您可能想看看 Google 的 Guava 库。

这可以为您计算 powerset 以及对 Collections 的任何其他操作，还可以确保良好的性能（考虑到您正在计算 powerset .....）。

score 0 · Accepted Answer

它具有许多您需要的实用程序，例如 powerSet 和交集。

4 回答 4