Групповые списки Python на основе повторяющихся позиций

Question

Этот вопрос очень похож на этот Group Python list of lists into groups based on overlapping items, на самом деле его можно назвать дубликатом.

В принципе, у меня есть список подписок, в которых каждый под-список содержит некоторое количество целых чисел (этот номер не является одинаковым среди подписок). Мне нужно сгруппировать все под-списки, в которых есть одно целое число или больше.

Причина, по которой я задаю новый отдельный вопрос, заключается в том, что я пытаюсь адаптировать Martijn Pieters 'great answer без везения.

Вот MWE:

def grouper(sequence): 
    result = [] # will hold (members, group) tuples 

    for item in sequence: 
     for members, group in result: 
      if members.intersection(item): # overlap 
       members.update(item) 
       group.append(item) 
       break 
     else: # no group found, add new 
      result.append((set(item), [item])) 

    return [group for members, group in result] 


gr = [[29, 27, 26, 28], [31, 11, 10, 3, 30], [71, 51, 52, 69], 
     [78, 67, 68, 39, 75], [86, 84, 81, 82, 83, 85], [84, 67, 78, 77, 81], 
     [86, 68, 67, 84]] 

for i, group in enumerate(grouper(gr)): 
    print 'g{}:'.format(i), group 

и выход я получаю:

g0: [[29, 27, 26, 28]] 
g1: [[31, 11, 10, 3, 30]] 
g2: [[71, 51, 52, 69]] 
g3: [[78, 67, 68, 39, 75], [84, 67, 78, 77, 81], [86, 68, 67, 84]] 
g4: [[86, 84, 81, 82, 83, 85]] 

Последняя группа g4 должны были объединены с g3, так как списки внутри них разделяют элементы 81, 83 и 84, и даже один повторяющийся элемент должен быть достаточным для их объединения.

Я не уверен, неправильно ли я применяю код или что-то не так с кодом.

Answer 1

Вы можете описать слияние, которое хотите выполнить как заданную консолидацию или как проблему с подключенными компонентами. Я имею тенденцию использовать готовый алгоритм консолидации, а затем адаптировать его к конкретной ситуации. Например, IIUC, вы могли бы использовать что-то вроде

def consolidate(sets): 
    # http://rosettacode.org/wiki/Set_consolidation#Python:_Iterative 
    setlist = [s for s in sets if s] 
    for i, s1 in enumerate(setlist): 
     if s1: 
      for s2 in setlist[i+1:]: 
       intersection = s1.intersection(s2) 
       if intersection: 
        s2.update(s1) 
        s1.clear() 
        s1 = s2 
    return [s for s in setlist if s] 

def wrapper(seqs): 
    consolidated = consolidate(map(set, seqs)) 
    groupmap = {x: i for i,seq in enumerate(consolidated) for x in seq} 
    output = {} 
    for seq in seqs: 
     target = output.setdefault(groupmap[seq[0]], []) 
     target.append(seq) 
    return list(output.values()) 

, который дает

>>> for i, group in enumerate(wrapper(gr)): 
...  print('g{}:'.format(i), group) 
...  
g0: [[29, 27, 26, 28]] 
g1: [[31, 11, 10, 3, 30]] 
g2: [[71, 51, 52, 69]] 
g3: [[78, 67, 68, 39, 75], [86, 84, 81, 82, 83, 85], [84, 67, 78, 77, 81], [86, 68, 67, 84]] 

(заказ не гарантируется из-за использования словарей.)

Answer 2

Похоже, что если вы включите каждый дополнительный список в набор, вы заинтересованы в содержимом, а не в заказе, поэтому наборы - лучший выбор структуры данных. См. Так: http://rosettacode.org/wiki/Set_consolidation