检查列表是否是另一个列表的替换子，没有重新排列python

Question

我有一个大列表（〜200,000个元素），另一个列表的大小为1-9。我需要在大列表中找到最长的小列表。因此，我需要确定小列表是否为大列表的子集，且没有重复（即[a，a]是[a，b，c]的子集应返回False）。有办法吗？

我已经尝试过.issubset，但是对于重复项，它返回true。我还尝试检查小列表的每个排列，但这太慢了。

Answer 1

似乎您需要一个multiset（如使用set所建议），请使用collections.Counter：

from collections import Counter

short = ['a','a']
large =  ['a','b','c']

short_counts = Counter(short)
large_counts = Counter(large)

print(all(value <= large_counts.get(key, 0) for key, value in short_counts.items()))

输出

False

将所有内容放入函数并添加一些示例，我们得到：

def sub_multi_set(sh, la):
    short_counts = Counter(sh)
    large_counts = Counter(la)
    return all(value <= large_counts.get(key, 0) for key, value in short_counts.items())


print(sub_multi_set(['a', 'a'], ['a', 'b', 'c']))
print(sub_multi_set(['a'], ['a', 'b', 'c']))
print(sub_multi_set(['a', 'a'], ['a', 'a', 'a', 'b', 'c']))
print(sub_multi_set(['a', 'b'], ['a', 'b', 'c']))
print(sub_multi_set(['d', 'b'], ['a', 'b', 'c']))

输出

False
True
True
True
False