用于确定集合是否是另一集合的子集的有效代码

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

您可能希望在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将从中删除所有集合,这些集合是列表中位于它们之前的其他集合的子集或副本.

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