python: как объединить список в кластеры?

Question

У меня есть список кортежей:

[(3,4), (18,27), (4,14)]

, и мне нужен код, объединяющий кортежи с повторяющимися номерами, создающий другой список, в котором все элементы списка будут содержать только уникальные номера.Список должен быть отсортирован по длине кортежей, то есть:

>>> MergeThat([(3,4), (18,27), (4,14)])
[(3,4,14), (18,27)]

>>> MergeThat([(1,3), (15,21), (1,10), (57,66), (76,85), (66,76)])
[(57,66,76,85), (1,3,10), (15,21)]

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

Существует ли относительно простой код для функции MergeThat ()?

Answer 1

Я очень старался выяснить это, но только после того, как я попробовал подход, ответ Яна (спасибо!) Предположил, что я понял, в чем заключается теоретическая проблема: вход представляет собой список ребер и определяет график. Мы ищем сильно связанные компоненты этого графа. Все просто.

Хотя вы можете сделать это эффективно , на самом деле нет причин для реализации этого самостоятельно! Просто импортируйте хорошую библиотеку графиков :

import networkx as nx

# one of your examples
g1 = nx.Graph([(1,3), (15,21), (1,10), (57,66), (76,85), (66,76)])
print nx.connected_components(g1) # [[57, 66, 76, 85], [1, 10, 3], [21, 15]]

# my own test case
g2 =  nx.Graph([(1,2),(2,10), (20,3), (3,4), (4,10)])
print nx.connected_components(g2) # [[1, 2, 3, 4, 10, 20]]

Answer 2

import itertools

def merge_it(lot):
    merged = [ set(x) for x in lot ] # operate on sets only
    finished = False
    while not finished:
        finished = True
        for a, b in itertools.combinations(merged, 2):
            if a & b:
                # we merged in this iteration, we may have to do one more
                finished = False
                if a in merged: merged.remove(a)
                if b in merged: merged.remove(b)    
                merged.append(a.union(b))
                break # don't inflate 'merged' with intermediate results
    return merged

if __name__ == '__main__':
    print merge_it( [(3,4), (18,27), (4,14)] )
    # => [set([18, 27]), set([3, 4, 14])]

    print merge_it( [(1,3), (15,21), (1,10), (57,66), (76,85), (66,76)] )
    # => [set([21, 15]), set([1, 10, 3]), set([57, 66, 76, 85])]

    print merge_it( [(1,2), (2,3), (3,4), (4,5), (5,9)] )
    # => [set([1, 2, 3, 4, 5, 9])]

Вот фрагмент (включая doctests): http://gist.github.com/586252

Answer 3

def collapse(L):
    """ The input L is a list that contains tuples of various sizes.
        If any tuples have shared elements, 
        exactly one instance of the shared and unshared elements are merged into the first tuple with a shared element.
        This function returns a new list that contain merged tuples and an int that represents how many merges were performed."""
    answer = []
    merges = 0
    seen = []   # a list of all the numbers that we've seen so far
    for t in L:
        tAdded = False
        for num in t:
            pleaseMerge = True
            if num in seen and pleaseMerge:
                answer += merge(t, answer)
                merges += 1
                pleaseMerge = False
                tAdded= True
            else:
                seen.append(num)
        if not tAdded:
            answer.append(t)

    return (answer, merges)

def merge(t, L):
    """ The input L is a list that contains tuples of various sizes.
        The input t is a tuple that contains an element that is contained in another tuple in L.
        Return a new list that is similar to L but contains the new elements in t added to the tuple with which t has a common element."""
    answer = []
    while L:
        tup = L[0]
        tupAdded = False
        for i in tup:
            if i in t:
                try:
                    L.remove(tup)
                    newTup = set(tup)
                    for i in t:
                        newTup.add(i)
                    answer.append(tuple(newTup))
                    tupAdded = True
                except ValueError:
                    pass
        if not tupAdded:
            L.remove(tup)
            answer.append(tup)
    return answer

def sortByLength(L):
    """ L is a list of n-tuples, where n>0.
        This function will return a list with the same contents as L 
        except that the tuples are sorted in non-ascending order by length"""

    lengths = {}
    for t in L:
        if len(t) in lengths.keys():
            lengths[len(t)].append(t)
        else:
            lengths[len(t)] = [(t)]

    l = lengths.keys()[:]
    l.sort(reverse=True)

    answer = []
    for i in l:
        answer += lengths[i]
    return answer

def MergeThat(L):
    answer, merges = collapse(L)
    while merges:
        answer, merges = collapse(answer)
    return sortByLength(answer)

if __name__ == "__main__":
    print 'starting'
    print MergeThat([(3,4), (18,27), (4,14)])
    # [(3, 4, 14), (18, 27)]
    print MergeThat([(1,3), (15,21), (1,10), (57,66), (76,85), (66,76)])
    # [(57, 66, 76, 85), (1, 10, 3), (15, 21)]

Answer 4

Это не эффективно для огромных списков.

def merge_that(lot):
   final_list = []
   while len(lot) >0 :
      temp_set = set(lot[0])
      deletable = [0]      #list of all tuples consumed by temp_set
      for i, tup2 in enumerate(lot[1:]):
         if tup2[0] in temp_set or tup2[1] in temp_set:
            deletable.append(i)
            temp_set = temp_set.union(tup2)
      for d in deletable:
         del lot[d]
      deletable = []
      # Some of the tuples consumed later might have missed their brothers
      # So, looping again after deleting the consumed tuples
      for i, tup2 in enumerate(lot):
         if tup2[0] in temp_set or tup2[1] in temp_set:
            deletable.append(i)
            temp_set = temp_set.union(tup2)
      for d in deletable:
         del lot[d]
      final_list.append(tuple(temp_set))
   return final_list

Это выглядит ужасно, но работает.

Answer 5

Код, написанный другими, наверняка сработает, но есть еще один вариант, возможно, более простой для понимания и, возможно, с меньшей алгоритмической сложностью.

Сохранение словаря от чисел к кластеру (реализованному как набор питонов), членом которого они являются. Также включите этот номер в соответствующий набор. Обработать входную пару как:

1. Ни один элемент не находится в словаре: создайте новый набор, подключите словарные ссылки соответствующим образом.
2. Один или другой, но не оба элемента находятся в словаре: добавьте еще невидимый элемент к набору его брата и добавьте ссылку на словарь в правильный набор.
3. Оба элемента видны ранее, но в разных наборах: возьмите объединение старых наборов и обновите все словарные ссылки на новый набор.
4. Вы уже видели обоих участников, и они в одном наборе: ничего не делать.

После этого просто соберите уникальные значения из словаря и отсортируйте их в порядке убывания размера. Эта часть задания составляет O (m log n) и поэтому не будет доминировать во время выполнения.

Это должно работать за один проход. Написание фактического кода оставлено читателю в качестве упражнения.

Answer 6

Вот еще одно решение, которое не использует itertools и использует другой, немного более подробный подход.Сложность этого решения заключается в объединении наборов кластеров, когда t0 in index and t1 in index.

import doctest

def MergeThat(a):
    """ /3089525/python-kak-obedinit-spisok-v-klastery

    >>> MergeThat([(3,4), (18,27), (4,14)])
    [(3, 4, 14), (18, 27)]
    >>> MergeThat([(1,3), (15,21), (1,10), (57,66), (76,85), (66,76)])
    [(57, 66, 76, 85), (1, 3, 10), (15, 21)]
    """
    index = {}
    for t0, t1 in a:
        if t0 not in index and t1 not in index:
            index[t0] = set()
            index[t1] = index[t0]
        elif t0 in index and t1 in index:
            index[t0] |= index[t1]
            oldt1 = index[t1]
            for x in index.keys():
                if index[x] is oldt1:
                    index[x] = index[t0]
        elif t0 not in index:
            index[t0] = index[t1]
        else:
            index[t1] = index[t0]
        assert index[t0] is index[t1]
        index[t0].add(t0)
        index[t0].add(t1)
    return sorted([tuple(sorted(x)) for x in set(map(frozenset, index.values()))], key=len, reverse=True)

if __name__ == "__main__":
    import doctest
    doctest.testmod()