分组集算法

Question

需要开发一个算法来解决以下任务。

给定：

The N sets with a different number of elements

预期结果：

The new M sets containing ≥X common elements of the N sets

例子：

N1=[1,2,3,4,5]
N2=[2,3,5]
N3=[1,3,5]
N4=[1,2]

if X=3:

M1=[1] (from N1,3,4)
M2=[2] (from N1,2,4)
M3=[3,5] (from N1,2,3)

- Roman Koblev

---

相关：https://dev59.com/2FHTa4cB1Zd3GeqPPCnN - Ian Mercer

凭直觉想：对输入集合中的元素进行排序。然后使用合并匹配来遍历每个存在的整数，计算每个整数的出现次数。那些 Count >= X 的整数放入 M 集合中。对于每个这样的整数，使用二进制编码在 N 集合成员身份上，以便将成员分组到 M 集合中。 - RBarryYoung

新的M集合是否不相交？ - 象嘉道

相关内容：https://dev59.com/55bfa4cB1Zd3GeqP1fy7 - hilberts_drinking_problem

Answer 1

给定N个已排序整数集（记为Ni），初始化N个变量Hi，它们将保存每个集合的头部。

只要还存在未达到各自Ni末尾的索引Hi，就遍历值Vi=Ni[Hi]并找到最小值Vmin，计算出现次数n并存储相应的索引j（可以在一个循环中完成所有操作）。

增加Hj。

如果n>X，则会得到一个新集合M = [Vmin] (来自Nj)。

按照您的意愿对数据表示进行建模，以便使用(来自Nj)作为映射键。

- OB1