确定一组是否为另一组子集的有效代码

[poster]

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

示例：设置A = [1 2 3 4]设置B = [4 3]设置C = [3 4 1]设置D = [4 3 2 1]

输出应为：Set A

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

因此，有两个基本规则：1.如果一个集合是另一个集合的子集，则将其删除2.如果一个集合的元素与先前集合的元素相同，则删除一个集合

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

建议非常欢迎！

补充说明：问题在于，使用大量集合时，将存在大量成对比较。



回答：

您可能需要看一下MATLAB中的内置set操作函数 。如果不需要，为什么还要重新发明轮子呢？ ;）

提示： 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 nSets-1集合比较。在最坏的情况下，内部循环永不中断，它将执行(nSets-1)*nSets/2组比较。



更多&回答...