再加上有一個列表的列表至少在常見的一些列表，Python的

Question

考慮列出的這份名單：

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

我想所有有共同的至少一個數字的名單組合，即將會迭代完成，直到完成，沒有dubletters會一起去。結果將是：

combine(l) = [ [1,2,3,4], [5,6,7,8,9] ] 

是否有任何干淨的方式來做到這一點，也許與itertools？

Answer 1

out = [] 
for l in lists: 
    for o in out: 
     if set(l).intersection(set(o)): 
      o[:] = list(set(l) + set(o)) # Mutate, don't reassign temp var 
      break 
    else: 
     out.append(l) 

不完美的書面，可以優化，不排序，但應該給你如何做到這一點的想法。

Answer 2

我天真的嘗試：

1. 合併時，它們的交集不是空
2. 排序每個元組
3. 刪除重複的元組
4. 重複這一點，直到不再有變化的所有元組。

---

例子：

def combine_helper(l): 
    l = map(set, l) 
    for i, x in enumerate(l, 1): 
     x = set(x) 
     for y in l[i:]: 
      if x & y: 
       x = x | y 
     yield tuple(sorted(x)) 

def combine(l): 
    last_l = [] 
    new_l = l 
    while last_l != new_l: 
     last_l = new_l 
     new_l = list(set(combine_helper(last_l))) 
    return map(list, last_l) 

l = [ [1], [1], [1,2,3], [4,1], [5], [5], [6], [7,8,9], [7,6], [8,5] ] 
print combine(l) 

輸出：

$ python test.py 
[[1, 2, 3, 4], [5, 6, 7, 8, 9]] 

Answer 3

遞歸來救援！不要忘記減少！

input_list = [ [1], [1], [1, 2, 3], [4, 1], [5], [5], [6], [7, 8, 9], 
       [7, 6], [8, 5] ] 
def combine(input_list): 
    input_list = map(set, input_list) # working with sets has some advantages 
    reduced_list = reduce(combine_reduce, input_list, []) 
    if len(reduced_list) == len(input_list): 
     # return the whole thing in the original format (sorted lists) 
     return map(sorted, map(list, reduced_list)) 
    else: 
     # recursion happens here 
     return combine(reduced_list) 

def combine_reduce(reduced_list, numbers): 
    ''' 
    find the set to add the numbers to or append as a new set. 
    ''' 
    for sub_set in reduced_list: 
     if sub_set.intersection(numbers): 
      sub_set.update(numbers) 
      return reduced_list 
    reduced_list.append(numbers) 
    return reduced_list 

print combine(input_list) 

打印出：

$ python combine.py 
[[1, 2, 3, 4], [5, 6, 7, 8, 9]] 

我們有兩件事情會在這裏。第一個是reduce：我使用它來製作列表，通過將每個元素放置在某個地方的結果列表中或附加它，如果這樣做不起作用。儘管如此，這並不能完成整個工作，所以我們重複這個過程（遞歸！）直到減少不提供一個較短的列表。

同樣，使用set允許方便intersection方法。您會注意到遞歸中map(set, input_list)的行是多餘的。從內功能combine_inner提取包裝函數combine和放置格式/非格式（從list到set和背面）在外部功能留給讀者作爲練習。

Answer 4

其可能引入以下嘗試：

1. 使1-元素集與存在於列表中的單個值的列表。這是輸出列表。
2. l列表是應該如何連接輸出列表中的項目的配方。例如如果輸出列表是[{1}, {2}, {3}]，並且l列表中的第一個元素是[1,3]，則應該連接輸出列表中包含1和3的所有集合：output = [{1,3}, {2}]。
3. 對列表中的每個項目重複第2步。

代碼：

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

def compose(l): 
    # the following will convert l into a list of 1-element sets: 
    # e.g. [ {1}, {2}, ... ] 
    r = sum(l, []) 
    r = map(lambda x: set([x]), set(r)) 

    # for every item in l 
    # find matching sets in r and join them together 
    for item in map(set, l): 
     outside = [x for x in r if not x & item] # elements untouched 
     inside = [x for x in r if x & item]  # elements to join 
     inside = set([]).union(*inside)   # compose sets 
     r = outside + [inside] 
    return r 

例子：

>>> compose(l) 
[set([1, 2, 3, 4]), set([8, 9, 5, 6, 7])]