查找不相关的元素的最大子集

Question

我有一组整数，我想找到元素不以特定方式相互关联的最大子集。例如，如果元素中的任何元素乘以13，则结果不在子集中的子集。

我的第一个想法是迭代所有可能的子集，过滤掉不符合条件的子集，然后找到最大的子集，但这太慢了，我不知道如何生成所有可能的子集。

Answer 1

我将回答这个问题（来自评论）。一般来说，对于任何"相关性"都没有好的解决方案

关系如下：如果将子集中的任何元素乘以某个数字，则得到的数字不必在子集中。

如果您的号码是m

您可以生成所有链x、x*m、x*m*m。。。。，使得链中的所有数字都在集合中，x/m不是

从原始集合中每隔一秒删除一个元素，即x*m^2、x*m^4。剩下的元素就是你的目标集。

Answer 2

更好的方法是构建一个图，找到具有大多数边的顶点并将其移除，直到去除所有边。复杂性大约是O（N^2）。

下面是一个详细的算法：

for each possible pair (x, y) from the source set
begin
    if x = y * 13 or y = x * 13 then make edge between x and y
end
while graph has edges
begin
    let V = find: a vertex with maximum count of edges (it can be 1 or 2)
    remove V from the graph
end
result: the remaining vertexes in the graph