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

我有一个包含多个列表的列表。这些列表可以包含整数元素范围从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]]

任何想法？

来源

2015-02-07 Abs

您能否将最终的预期输出添加到完整的问题中？另外，你到目前为止尝试过什么？ – 2015-02-07 21:29:46

@MartijnPieters除非他只包含从他最长的名单缺少数字的短名单，像'[9]' – aneroid 2015-02-07 21:32:26

对不起我不是清楚，我改变了清单，并增加了输出 – Abs 2015-02-07 21:36:50

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

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

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]]

来源

2015-02-07 21:38:44

只是为了学习，你能解释一下为什么它是'0（nlogn）'？谢谢。 – ozgur 2015-02-07 21:46:05

@ozgurv：它是[计算复杂度]（http://en.wikipedia.org/wiki/Computational_complexity_theory）的度量，代码将执行多少个步骤作为N（输入的长度）执行的上限到无穷远。我用了一种排序，[Timsort有一个O（NlogN）上限]（http://en.wikipedia.org/wiki/Timsort）;这意味着代码的其余部分，这是一个直的O（N）循环将不再确定代码运行需要多长时间的上限。 – 2015-02-07 21:49:15

@ozgurv：如果打算将输入列表中的每个元素与其他元素进行比较，那么您会得到一个O（N ** 2）二次算法，每次将1个元素添加到列表的长度计算时间会增加一倍，而这个计算时间将会增加1 + log（n）个步长，比O（N）略微增加，这将随着元素的增加而线性缩放。 – 2015-02-07 21:50:46

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)

来源

2015-02-07 21:39:09

@MartijnPieters，是的，但考虑到提供的努力量我认为这是一个合理的答案 – 2015-02-07 21:43:06

这就是我想说当我看到你有一个downvote。 – 2015-02-07 21:43:28

实际上，如果有仅与'[5,6]'列表重叠的子列表，我不确定您的解决方案是否正确。如果在'l'中有一个'[5]'或'[6]'子列表，你的代码不会消除它。 – 2015-02-07 21:44:53

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

选项2：转换（复制）的每个列表的成set秒。选择你的最大集合A并减去其他每个B。如果A - B的结果长度小于A的长度，则丢弃由B表示的列表。如果结果与A的长度相同，则B中的所有项目都是唯一的（不在A中），因此不要丢弃B。

来源

2015-02-07 21:43:35 aneroid

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

回答

相关问题