一个高效的代码来确定一个集合是否是另一个集合的子集

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代码在执行此操作时效率不高 - 它主要由嵌套循环组成。

欢迎提出建议！

附加解释：问题在于有大量的集合时，会进行非常多的成对比较。

- Eduardas

---

你知道这个集合的元素吗？它们只是整数吗？它们只在某个范围内吗？如果是这样，考虑设置一个一维布尔（二进制）数组，每个元素对应于A中的一个整数。首先遍历A以形成此数组，然后遍历B以检查B中的每个元素是否在A中（只需查看数组中的标志是否为true）。如果这些都是已知范围内的整数，则效率应该在O(n)左右。如果它们不是整数或范围未知，则哈希方案可以以类似的方式工作。 - Assaf

是的，它们只能是整数。集合的最大大小也已知。 - Eduardas

你是否确实验证了配对比较占用太多时间的问题？通过按大小对集合进行排序，可以减少比较次数，因为如果B的大小小于或等于A，则B只能是A的子集。 - Marc

你对集合 { [1,2], [3,4] } 所期望的操作是什么？你是想要返回空集合（“没有任何一个集合是所有集合的超集”），还是想要返回{[1,2],[3,4]}（“所有的集合都是这些集合的子集”）？ - Eric Towers

Answer 1

你可能会想要查看 MATLAB 内置的set operation functions。如果不必要，为什么要重复发明轮子呢？ ;)

提示：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 次集合比较。

- gnovice

---

编写一个逻辑测试以检查集合是否为子集并不是问题所在。我想避免的是在集合之间进行大量的成对比较。例如，如果我将我的集合保存在矩阵中，我希望对整个矩阵应用操作以提取具有正确集合的行。 - Eduardas

@Edward：我已经更新了我的答案，并为您提供了完整的解决方案。希望它比您之前尝试的更有效率。 ;) - gnovice

Answer 2

我认为你想要问的问题是“给定一个集合列表，挑选出包含其他所有集合的集合”。有许多边缘情况，我不知道你想要什么输出（例如A = { 1, 2 }和B = { 3, 4 }），因此你需要澄清很多。

然而，为了回答你提出的问题，关于集合包容性，你可以使用集合差异（等价于与另一个集合相对补集）。在Mathematica中，这样的事情：

setA = {1, 2, 3, 4};
setB = {4, 3};
setC = {3, 4, 1};
setD = {4, 3, 2, 1};
Complement[setD, setA] == {}
 True

表示 setD 是 setA 的子集。

- Jonathan

---

我在上面添加了一些澄清。输出应该设置为A，因为它包含集合B和C，而集合D只是重新排列的集合A。此外，问题不在于设计逻辑测试以检查集合是否为子集，而在于避免进行大量的成对比较。因此，我的问题更多地涉及到解决问题的有效方法。 - Eduardas

Answer 3

假设如果没有一个集合是所有提供的集合的超集，您希望返回空集。（即如果没有一个集合是所有集合的超集，则返回“无”）

因此，...，您想要取所有集合的并集，然后在列表中找到具有相同元素数量的第一个集合。这并不太难，跳过将输入重新格式化为内部列表形式的步骤... Mathematica：

    topSet[a_List] := Module[{pool, biggest, lenBig, i, lenI},  
        pool = DeleteDuplicates[Flatten[a]];  
        biggest = {}; lenBig = 0;  
        For[i = 1, i <= Length[a], i++,  
            lenI = Length[a[[i]]];  
            If[lenI > lenBig, lenBig = lenI; biggest = a[[i]]];  
            ];  
        If[lenBig == Length[pool], biggest, {}]  
    ]  

例如：

topSet[{{1,2,3,4},{4,3},{3,4,1},{4,3,2,1}}]  
  {1,2,3,4}  
topSet[{{4, 3, 2, 1}, {1, 2, 3, 4}, {4, 3}, {3, 4, 1}}]  
  {4,3,2,1}  
topSet[{{1, 2}, {3, 4}}]  
  {}
作为一项大型测试：
<<Combinatorica`
Timing[Short[topSet[Table[RandomSubset[Range[10^3]], {10^3}]]]]
{14.64, {}}
也就是说，在14.64秒内分析了一个由1000个随机选择的子集组成的集合（毫不奇怪，它们中没有一个是所有子集的超集）。
--编辑-转义了隐藏了一些实现细节的小于号。另外...
运行时间分析：设L为列表数，N为所有列表中元素总数（包括重复项）。池分配需要O（L）用于列表展平和O（N）用于删除重复项。在for循环中，所有对lenI的L个赋值累计需要O（N）的时间，而所有L个条件语句最多需要O（L）的时间。其余部分为O（1）。由于L < N，总运行时间为O（L）+ O（N）+ O（N）+ O（L）+ O（1），即O（N）。也就是说，如果超集存在，则可以在与输入长度成比例的时间内找到它-即各个集合长度之和。大O背后隐藏的常数并不大。

正确性证明：如果存在一个超集，那么它(1)包含自身，(2)包含其任何排列，(3)包含任何(其他)集合中存在的每个元素，(4)与集合中的任何其他集合一样长或更长。 结果：超集(如果存在)是集合中最长的集合，任何其他相同长度的集合都是它的排列，并且它包含任何集合中包含的每个元素的副本。 因此，如果有一个与集合的并集一样大的集合，则存在一个超集。

- Eric Towers

Answer 4

在Mathematica中，我建议使用Alternatives来实现这一点。

例如，如果我们有一个集合{1, 2, 3, 4}，并且我们希望测试集合x是否是子集，我们可以使用：MatchQ[x, {(1|2|3|4) ..}]。这种构造的优点是，一旦找到不属于集合的元素，测试就会停止并返回False。

我们可以将这种方法打包如下：

maximal[sets_] :=
  Module[{f},
    f[x__] := (f[Union @ Alternatives @ x ..] = Sequence[]; {x});
    f @@@ sets
  ]

maximal @ {{1, 2, 3, 4}, {4, 3}, {5, 1}, {3, 4, 1}, {4, 3, 2, 1}}

{{1, 2, 3, 4}, {5, 1}}

- Mr.Wizard