php - 如何确定一个列表是否是另一个列表的子集？

Question

确定一个列表是否是另一个列表的子集的有效方法是什么？

例子:

is_subset(List(1,2,3,4),List(2,3))    //Returns true
is_subset(List(1,2,3,4),List(3,4,5))  //Returns false

我主要是在寻找有效的算法，而不是太关心列表的存储方式。它可以存储在数组、链表或其他数据结构中。

谢谢

编辑:列表已排序

Answer 1

以下是您可以进行的一些权衡。让我们假设你有两组元素，S 和 T，从一个宇宙 U 中抽取出来。我们想确定是否 S≥T。在给定的示例之一中，我们有

S={1,2,3,4}
T={3,4,5}
U={1,2,3,4,5}

1.排序列表(或平衡搜索树)
大多数海报建议的方法。如果您已经有排序列表，或者不关心创建它们所需的时间长度(例如，您不经常这样做)，那么该算法基本上是线性时间和空间。这通常是最好的选择。

(为了公平对待这里的其他选择，时间和空间界限实际上应该在适当的地方包含“Log |U|”的因素，但这通常是不相关的)

数据结构:S 和 T 中的每一个的排序列表。 或者可以在恒定空间中迭代的平衡搜索树(例如 AVL 树、红黑树、B+-树)。

算法:对于 T 中的每个元素，依次线性搜索 S 中的该元素。记住您从哪里停止每次搜索，然后从那里开始下一次搜索。如果每次搜索都成功，则 S≥T。

时间复杂度:大约 O( |S| Log|S| + |T| Log|T| ) 创建排序列表， O( max(|S|, |T|) ) 进行比较。

空间复杂度:大约 O( |S| + |T| )

示例 (C++)

#include <set>
#include <algorithm>

std::set<int> create_S()
{
    std::set<int> S;
    // note: std::set will put these in order internally
    S.insert(3);
    S.insert(2);
    S.insert(4);
    S.insert(1);
    return S;
}

std::set<int> create_T()
{
    std::set<int> T;
    // note std::set will put these in order internally
    T.insert(4);
    T.insert(3);
    T.insert(5);
    return T;
}

int main()
{
    std::set<int> S=create_S();
    std::set<int> T=create_T();
    return std::includes(S.begin(),S.end(), T.begin(), T.end());
}

2. 哈希表
使用哈希表可以获得比排序列表更好的平均时间复杂度。大集合的改进行为是以小集合通常较差的性能为代价的。

与排序列表一样，我忽略了宇宙大小带来的复杂性。

数据结构:S 的哈希表，T 的任何可快速迭代的东西。

算法:将 S 的每个元素插入其哈希表。然后，对于 T 中的每个元素，检查它是否在哈希表中。

时间复杂度:O( |S| + |T| ) 设置，O( |T| ) 比较。

空间复杂度:O( |S| + |T| )

示例 (C++)

#include <tr1/unordered_set>

std::tr1::unordered_set<int> create_S()
{
    std::tr1::unordered_set<int> S;
    S.insert(3);
    S.insert(2);
    S.insert(4);
    S.insert(1);
    return S;
}

std::tr1::unordered_set<int> create_T()
{
    std::tr1::unordered_set<int> T;
    T.insert(4);
    T.insert(3);
    T.insert(5);
    return T;
}

bool includes(const std::tr1::unordered_set<int>& S, 
              const std::tr1::unordered_set<int>& T)
{
    for (std::tr1::unordered_set<int>::const_iterator iter=T.begin();
         iter!=T.end();
         ++iter)
    {
        if (S.find(*iter)==S.end())
        {
            return false;
        }
    }
    return true;
}

int main()
{
    std::tr1::unordered_set<int> S=create_S();
    std::tr1::unordered_set<int> T=create_T();
    return includes(S,T);
}

3. 位集
如果你的宇宙特别小(假设你只能有 0-32 个元素)，那么位集是一个合理的解决方案。运行时间(同样，假设您不关心设置时间)基本上是恒定的。如果您确实关心设置，它仍然比创建排序列表更快。

不幸的是，即使是中等大小的宇宙，bitsets 也会很快变得笨拙。

数据结构:每个 S 和 T 的位 vector (通常是机器整数)。在给定的示例中，我们可能对 S=11110 和 T=00111 进行编码。

算法:计算交集，通过计算 S 中每个位与 T 中相应位的按位“与”。如果结果等于 T，则 S≥T。

时间复杂度:O( |U| + |S| + |T| ) 进行设置，O( |U| ) 进行比较。

空间复杂度:O( |U| )

示例:(C++)

#include <bitset>

// bitset universe always starts at 0, so create size 6 bitsets for demonstration.
// U={0,1,2,3,4,5}

std::bitset<6> create_S()
{
    std::bitset<6> S;
    // Note: bitsets don't care about order
    S.set(3);
    S.set(2);
    S.set(4);
    S.set(1);
    return S;
}

std::bitset<6> create_T()
{
    std::bitset<6> T;
    // Note: bitsets don't care about order
    T.set(4);
    T.set(3);
    T.set(5);
    return T;
}

int main()
{
    std::bitset<6> S=create_S();
    std::bitset<6> T=create_T();

    return S & T == T;
}

4. Bloom filters
bitsets 的所有速度优势，没有 bitsets 对宇宙大小的讨厌限制。只有一个缺点:他们有时(通常，如果你不小心的话)给出错误的答案:如果算法说“不”，那么你肯定没有包含。如果算法说"is"，您可能会也可能不会。通过选择较大的过滤器尺寸和良好的散列函数可以获得更好的准确性。

考虑到它们可以并且会给出错误的答案，布隆过滤器听起来可能是一个可怕的想法。但是，它们有明确的用途。通常，人们会使用 Bloom 过滤器快速进行许多包含检查，然后在需要时使用较慢的确定性方法来保证正确性。链接的维基百科文章提到了一些使用布隆过滤器的应用程序。

数据结构:A Bloom filter是一个花哨的位集。必须事先选择过滤器大小和哈希函数。

算法(草图):将bitset初始化为0。要添加一个元素到bloom filter，用每个hash函数对其进行hash，并在bitset中设置相应的bit。确定包含的工作就像对位集一样。

时间复杂度:O(过滤器大小)

空间复杂度:O(过滤器大小)

正确概率:如果它回答“S 不包括 T”，则始终正确。如果它回答“S 包括 T”，则类似于 0.6185^(|S|x|T|/(filter size)))。特别是，滤波器大小必须与 |S| 的乘积成正比。和|T|给出合理的准确概率。