摺疊列表以消除冗餘

我有幾個長列表的相關對象列表，我想分組以減少冗餘。僞代碼：摺疊列表以消除冗餘

>>>list_of_lists = [[1,2,3],[3,4],[5,6,7],[1,8,9,10]...] 
>>>remove_redundancy(list_of_lists) 
[[1,2,3,4,8,9,10],[5,6,7]...]

因此，包含相同元素的列表將摺疊爲單個列表。摺疊它們很容易，一旦我找到列表進行組合，我可以使列表成爲集合，並採取他們的聯合，但我不知道如何比較列表。我需要做一系列for循環嗎？

我的第一個想法是，我應該循環查看子列表中的每個項目是否在任何其他列表中，如果是的話，合併列表然後重新開始，但這似乎非常低效。我做了一些搜索，發現這個：Python - dividing a list-of-lists to groups但我的數據不是結構化的。另外，我的實際數據是一系列字符串，因此無法從任何有意義的意義上排序。

我可以寫一些粗糙的循環代碼來完成這項工作，但我想知道是否有任何內置函數可以使這種比較更容易。也許在list comprehensions？

來源

2015-06-18 kevbonham

要清楚：如果任何兩個列表包含任何匹配的元素，您想要合併它們的元素？您是否有重複的元素，例如'[1，2，3]'和['1,5]'？一般來說，你應該看看使用元組和列表而不是列表來表示這種事情 – YXD

我也對YXD有同樣的問題 - 你想要移除什麼樣的冗餘？ – user1941126

@YXD - 對你的第一個問題，是的。如果我的例子中還有一個'[1,5]'列表，那麼所有的元素都應該放在一個列表中。最後，我基本上想要一系列的集合（任何地方都沒有重複），但是我最初的數據可能在列表中有重複。也許我應該解釋我的數據實際上是什麼樣子/它來自哪裏......將在一秒內發佈一個編輯。 – kevbonham

我認爲這是一個合理有效的方法，如果我正確理解你的問題。這裏的結果將會是一組列表。

也許知識的缺失位爲d & g（也寫作d.intersection(g)）尋找交集，與事實空集是「falsey」在Python

data = [[1,2,3],[3,4],[5,6,7],[1,8,9,10]] 

result = [] 

for d in data: 
    d = set(d) 

    matched = [d] 
    unmatched = [] 
    # first divide into matching and non-matching groups 
    for g in result: 
     if d & g: 
      matched.append(g) 
     else: 
      unmatched.append(g) 
    # then combine all matching groups into one group 
    # while leaving unmatched groups intact 
    result = unmatched + [set().union(*matched)] 

print(result) 
# [set([5, 6, 7]), set([1, 2, 3, 4, 8, 9, 10])]

我們從沒有組沿全部（result = []）。然後我們從數據中獲取第一個列表。然後我們檢查現有的組中的哪一個與該列表相交，哪些不相交。然後我們合併所有這些匹配組以及列表（通過以matched = [d]開始實現）。我們不會觸及不匹配的組（儘管也許其中一些最終會在以後的迭代中被合併）。如果您在每個循環中添加一行print(result)，您應該能夠看到它是如何構建的。在matched

所有集合的並通過set().union(*matched)計算。供參考：

來源

2015-06-18 14:28:07 YXD

這就是我想要的。我在'data'的末尾加了'[11]，[11，12]，[13]'，它會生成兩個附加的集合，但是如果我還添加'[12,5]'，它會將'11'和'12'到[5,6,7]'的集合中。正是我想要的......不知道我理解了所有的步驟，但我認爲我現在可以解開它。謝謝！ – kevbonham

太棒了！我添加了更多解釋性文字。 – YXD

解釋有很大的幫助，但仍然在用'set（）。union（* matched）'做的事情掙扎了一下。然後，我爲每個循環印刷了「匹配」和「不匹配」，並且都變得清晰了！再次感謝您的幫助！ – kevbonham

我假設你要合併包含任何共同的元素列表。

這裏是（根據==運營商）

import functools #python 2.5+ 
def seematch(X,Y): 
    return functools.reduce(lambda x,y : x|y,functools.reduce(lambda x,y : x+y, [[k==l for k in X ] for l in Y]))

，將會變得更快，如果你看起來有效（據我所知）如果有兩個列表包含至少一個共同的元素的功能找到「真」這裏描述的時候會用減少可中斷： Stopping a Reduce() operation mid way. Functional way of doing partial running sum

我試圖找到一種優雅的方式具有到位後，迭代速度快，但我認爲一個好的辦法是簡單地循環一次並創建一個包含「mer」的其他容器ged「列表。您在原始列表中包含的列表以及在代理列表中創建的每個新列表上循環一次。

話雖如此 - 看起來可能有更好的選擇 - 看看你是否可以通過前面的步驟，通過某種簿記來消除冗餘。

我知道這是一個不完整的答案 - 希望無論如何幫助！

來源

2015-06-18 14:52:49 user1941126

最近我搜索了一些我的問題的答案已經產生了lambda函數和'reduce'（也是'map'）的結果，我根本不明白。很顯然，我需要回去做一些關於這個主題的基本閱讀 - 我拼湊在一起的編程知識顯然是不完整的。 – kevbonham

摺疊列表以消除冗餘

回答

相關問題