查找列表的索引，该列表是列表列表中的子集

Question

我有两个非常大的列表列表（500万的顺序）。

例如：

1) 第一个列表 a 总是包含 8 个元素的列表。

2) 第二个列表 b 始终包含 4 个元素的列表。

对于 b 中的每个列表，可能有多个子集，但这不是问题。

a=[[0 1 10 9 369 370 379 378],[1 2 11 10 370 371 380 379]..[[0 1 10 9 365 370 379 400]]

b=[[0 1 370 369],[1 2 371 370], ......]

我想知道 b 中的每个列表在 a 中包含其所有元素的列表的索引。

例如：我知道 "b[0]=[ 0 1 370 369]" 是 "a[0]=[0 1 10 9 369 370 379 378]" 的子集，因为 b[0] 中的所有元素都包含在 a[0] 中。 b[1] 是 a[1] 的子集也是如此。

所以我想要这样的输出：c=[[0],[1].......].

如果有多个子集，我应该得到类似这样的内容：c=[[0],[1].....[20,19].....]

我的问题是我的代码太慢了：

index=[]
for i in range(len(b)):
    for j in range(len(a)):
        if set(b[i])<set(a[j]):
        print b[i]
        print a[j]
        print j
        index.append([j]) #index in a

这是我的代码的输出：

[  0   1 370 369]
[  0   1  10   9 369 370 379 378]
0

[  1   2 371 370]
[  1   2  11  10 370 371 380 379]
1

.
.
[369 370 739 738]
[369 370 379 378 738 739 748 747]
320
.
.

在循环结束时 len(index)=len(b) 因为我确定 b 中的每个列表总是 a 的子集。

每次迭代最多需要 30/40 秒。

我确定有更 pythonic 的方式来执行相同的循环，我怎样才能加快它的速度？

谢谢

Answer 1

构建一个字典，显示 a 中的哪些列表包含每个数字：

import collections
number_locations = collections.defaultdict(set)
for i, l in enumerate(a):
    for num in l:
        number_locations[num].add(i)

然后对于 b 中的每个列表，查找在 a 中可以找到其元素的位置，并采用集合交集来查找 a 中的哪些元素包含所有 4 个数字：

index = [set.intersection(*[number_locations[num] for num in l]) for l in b]

这会生成一个集合列表；如果你真的需要列表，你可以在项目上调用 list，或者 sorted 来获取排序的索引列表。

查找列表的索引，该列表是列表列表中的子集

Find the index of a list which is subset in a list of list

python

list

subset