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

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≥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的哈希表,任何可以快速迭代的东西.

算法:将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),那么bitset是一个合理的解决方案.运行时间(再次,假设您不关心设置时间)基本上是不变的.在您关心设置的情况下,它仍然比创建排序列表更快.

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

数据结构:S和T中的每一个的位向量(通常是机器整数).在给定的示例中,我们可以编码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过滤器
bitset的所有速度优势,没有bitset所具有的宇宙大小的令人讨厌的限制.只有一个缺点:他们有时(通常,如果你不小心)给出错误的答案:如果算法说"不",那么你肯定没有包含.如果算法说"是",您可能会也可能不会.通过选择较大的滤波器大小和良好的散列函数可以获得更高的精度.

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

数据结构:Bloom过滤器是一个花哨的bitset.必须事先选择过滤器大小和散列函数.

算法(草图):将bitset初始化为0.要将一个元素添加到bloom过滤器,请使用每个哈希函数对其进行哈希处理,并在bitset中设置相应的位.确定包含就像bitset一样.

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

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

正确性概率:如果答案为"S不包含T",则始终正确.如果它回答"S包括T",那么像0.6185 ^(| S | x | T | /(过滤器大小))).特别是,必须根据| S |的乘积选择滤波器大小 和| T | 给出合理的准确概率.

Answer 2

对于C++,最好的方法是使用std::includes算法:

#include <algorithm>

std::list<int> l1, l2;
...
// Test whether l2 is a subset of l1
bool is_subset = std::includes(l1.begin(), l1.end(), l2.begin(), l2.end());

这需要按照您的问题中的规定对两个列表进行排序.复杂性是线性的.

Answer 3

只是想提一下Python有一个方法:

return set(list2).issubset(list1)

要么:

return set(list2) <= set(list1)

Answer 4

如果两个列表都是有序的,一个简单的解决方案是同时遍历两个列表(两个列表中有两个凹凸指针),并验证第二个列表中的所有元素是否出现在第一个列表中(直到找到所有元素) ,或直到你在第一个列表中达到更大的数字).

C++中的伪代码看起来像这样:

List l1, l2;
iterator i1 = l1.start();
iterator i2 = l2.start();
while(i1 != l1.end() && i2 != l2.end()) {
  if (*i1 == *i2) {
    i1++;
    i2++;
  } else if (*i1 > *i2) {
    return false;
  } else {
    i1++;
  }
}
return true;

(它显然不会按原样运作,但这个想法应该是明确的).

如果未对列表进行排序,则可以使用哈希表 - 在第一个列表中插入所有元素,然后检查第二个列表中的所有元素是否都显示在哈希表中.

这些都是算法的答案.在不同的语言中,有默认的内置方法来检查这一点.

Answer 5

如果您同意将数据存储在哈希集中，您可以简单地检查 list1 是否包含 list2 中每个 x 的 x 。list2 的大小将接近 O(n)。（当然你也可以对其他数据结构做同样的事情，但这会导致不同的运行时）。