algorithm - 如何将一组集合减少到没有元素是另一个元素的子集？

Question

首先:不，这不是作业!这适合我为游戏编写的求解器。我只是将问题简化为这个简洁的语句:

给定一组集合 S，找到并删除 S 中作为 S 其他元素子集的任何元素。

域

1 <= |S| <= C^K

1 <= |S_i| <= K

2 <= C <= 10

10 <= K <= 500

详情

S_i 是 [0, K) 的子集

min(|S_i|) >= log_C(|S|)

我目前的方法是通过我称之为“NatSet”的东西对 S 中的每个集合进行排序，它只是一个 bool[K]。然后我按 |S_i| 对 S 进行排序并执行 O(|S|^2) 搜索以查找作为其他元素子集的元素。不幸的是，这对于我的目标值 C=6 和 K=16*9 来说太慢了。

Answer 1

考虑到我无法尝试(set S 的输入对我来说是不可见的)并决定以下是否有帮助，我只能将它们称为一些提示:

1. 当比较两个集合时: 'diminished' 二分查找: 当你比较集合 A (x1...xn) 是否是集合 B 的子集时( y1...ym )，假设你找到 yk = x1 (n <= m)

       y1, y2, ...,yk, yk+1 ... ym
                   |
                  x1   
   

   然后你可以在[yk+1, ym]范围内搜索x2。其他都一样。

2. 选择两组以比较:选择大的(即 s1 和 sk，然后是 s1 和 sk-1)，你说你按大小排序，大的更有可能包含它。
3. Sort Si? 我不确定 sort S 是否可以提高性能，您可以尝试不排序或使用 max-heap (见提示 4)
4. 使用最大堆:将叶子与根和根的儿子之一进行比较……如图所示)。

如果叶子没有被移除(即，不是它父亲的子集)，只需将它从堆中移除，你就可以将它交换到叶子被移除的地方。 (如下图)

注意:使用堆不能保证所有子集都被删除。

1. 如何排序？:在您的情况下，counting sort 似乎是是一种合适的排序方式，即线性排序。

更多:

1.你说你在修剪树，你要Alpha–beta pruning ？

2。 Efficient list intersection algorithm

希望这对您有所帮助。