matlab - 确定一个集合是否是另一个集合的子集的有效代码

Question

我正在寻找一种有效的方法来确定一个集合是否是 Matlab 或 Mathematica 中另一个集合的子集。

例子: 集合 A = [1 2 3 4] 集合 B = [4 3] 集 C = [3 4 1] 设 D = [4 3 2 1]

输出应该是:集合A

集合 B 和 C 属于集合 A，因为 A 包含它们的所有元素，因此，它们可以被删除(集合中元素的顺序无关紧要)。集合 D 具有与集合 A 相同的元素，并且由于集合 A 在集合 D 之前，我想简单地保留集合 A 并删除集合 D。

所以有两个基本规则: 1.删​​除一个集合，如果它是另一个集合的子集 2. 如果一个集合的元素与之前集合的元素相同，则删除该集合

我的 Matlab 代码在执行此操作时效率不高 - 它主要由嵌套循环组成。

非常欢迎提出建议!

补充说明:问题是集合数量多的情况下，成对比较的数量会非常多。

Answer 1

您可能想看看内置的 set operation functions在 MATLAB 中。如果不需要，为什么要重新发明轮子？ ;)

提示:ISMEMBER您可能对功能特别感兴趣。

编辑:

这是使用嵌套循环解决此问题的一种方法，但设置它们以尝试减少潜在迭代次数。首先，我们可以使用Marc中的建议。的注释按元素的数量对集合列表进行排序，以便它们从大到小排列:

setList = {[1 2 3 4],...  %# All your sets, stored in one cell array
           [4 3],...
           [3 4 1],...
           [4 3 2 1]};
nSets = numel(setList);                       %# Get the number of sets
setSizes = cellfun(@numel,setList);           %# Get the size of each set
[temp,sortIndex] = sort(setSizes,'descend');  %# Get the sort index
setList = setList(sortIndex);                 %# Sort the sets

现在我们可以将循环设置为从列表末尾的最小集合开始，然后首先将它们与列表开头的最大集合进行比较，以增加我们快速找到超集的几率(即我们'重新依赖较大的集合更有可能包含较小的集合)。当找到超集时，我们从列表中删除子集并打破内部循环:

for outerLoop = nSets:-1:2
  for innerLoop = 1:(outerLoop-1)
    if all(ismember(setList{outerLoop},setList{innerLoop}))
      setList(outerLoop) = [];
      break;
    end
  end
end

运行上述代码后，setList 将从中删除所有集合，这些集合是列表中它们前面的其他集合的子集或副本。

在最好的情况下(例如，您问题中的示例数据)，每次第一次迭代后，内部循环都会中断，使用 ISMEMBER 仅执行 nSets-1 集合比较.在最坏的情况下，内部循环永远不会中断，它将执行 (nSets-1)*nSets/2 集合比较。