如何刪除列表中的列表，如果一個列表中的元素存在於另一列表中

我有一個包含多個列表的列表。這些列表可以包含整數元素範圍從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

如何刪除列表中的列表，如果一個列表中的元素存在於另一列表中

回答

相關問題