如果一个列表中的元素存在于另一个列表中，如何删除列表中的列表

Question

我有一个包含多个列表的列表。列表可能包含从 0 到 9 的整数元素，如果两个或多个列表具有共同元素，则删除较小长度的列表

[[0, 3, 7],
 [0, 3, 7, 9],
 [0, 2, 3, 4, 7, 8, 9],
 [2, 4, 8, 9],
 [2, 4, 7, 8, 9],
 [5, 6]]

输出应该是：

[[5, 6], [0, 2, 3, 4, 7, 8, 9]]

有什么想法吗？

Answer 1

按长度对输入列表进行排序，然后选取最长的列表并将其添加到输出中。从这个最长的列表创建一个集合，您可以根据它测试其他列表。与该集合相交的任何后续较短列表都将被丢弃。

如果您发现不相交的较短列表，请将其添加到输出中，并更新您的基础集；毕竟，现在相交的较短列表至少与输出中的一个或多个列表共享一个数字。继续直到测试完所有列表：

def eliminate_shorter(list_of_lists):
    inputlist = sorted(list_of_lists, key=len)
    outputlist = [inputlist.pop()]
    numbers = set(outputlist[0])
    for sublist in reversed(inputlist):
        if not numbers.intersection(sublist):
            numbers.update(sublist)
            outputlist.append(sublist)
    return outputlist

这是一个O(NlogN)复杂度的算法（因为初始排序）。

演示：

>>> sample = [[0, 3, 7], [0, 3, 7, 9], [0, 2, 3, 4, 7, 8, 9], [2, 4, 8, 9], [2, 4, 7, 8, 9], [5, 6]]
>>> def eliminate_shorter(list_of_lists):
...     inputlist = sorted(list_of_lists, key=len)
...     outputlist = [inputlist.pop()]
...     numbers = set(outputlist[0])
...     for sublist in reversed(inputlist):
...         if not numbers.intersection(sublist):
...             numbers.update(sublist)
...             outputlist.append(sublist)
...     return outputlist
... 
>>> eliminate_shorter(sample)
[[0, 2, 3, 4, 7, 8, 9], [5, 6]]

Answer 2

l = [[0, 3, 7], [0, 3, 7, 9], [0, 2, 3, 4, 7, 8, 9], [2, 4, 8, 9], [2, 4, 7, 8, 9], [5, 6]]

longest = max(l,key=len)
st = set(longest)
print([longest]+[ele for ele in l if not st.intersection(ele)])
[[0, 2, 3, 4, 7, 8, 9], [5, 6]]

捕捉重叠的子列表：

longest = max(l, key=len)

seen = set()
seen.update(longest)
out = [longest]
for sub in l:
    if not seen.intersection(sub):
        out.append(sub)
    seen.update(sub)

Answer 3

选项 1：嵌套迭代每个列表的元素并相互比较。（你明白了）。可能不是最有效的方法。

选项 2：将每个列表转换（复制）为 sets。选择你最大的一组 A 并减去其他每个 B。如果 A - B 的结果长度小于 A 的长度，则丢弃 B 表示的列表。如果结果的长度与 A 相同，那么 B 中的所有项目都是唯一的（而不是 A），所以不要丢弃 B.

如果一个列表中的元素存在于另一个列表中，如何删除列表中的列表

How to remove list with in a list if an element in one list is present in the other

python

list

python-3.4