Союз каждый набор, который имеет хотя бы одно пересечение с другими наборами из списка [duplicate]

Это медленнее, чем решение Niklas (я получил 3,9 с на test.txt вместо 0.5s для своего решения), но дает тот же результат и может быть проще реализовать, например. Fortran, так как он не использует множества, только сортировка общего количества элементов, а затем один проход через все из них.

Он возвращает список с идентификаторами объединенных списков, поэтому также сохраняется отслеживание пустых списков, они остаются невредимыми.

def merge(lsts):
        # this is an index list that stores the joined id for each list
        joined = range(len(lsts))
        # create an ordered list with indices
        indexed_list = sorted((el,index) for index,lst in enumerate(lsts) for el in lst)
        # loop throught the ordered list, and if two elements are the same and
        # the lists are not yet joined, alter the list with joined id
        el_0,idx_0 = None,None
        for el,idx in indexed_list:
                if el == el_0 and joined[idx] != joined[idx_0]:
                        old = joined[idx]
                        rep = joined[idx_0]
                        joined = [rep if id == old else id for id in joined]
                el_0, idx_0 = el, idx
        return joined

Вот мой ответ. Я не проверял его против сегодняшней партии ответов.

Алгоритмы на основе пересечений - это O (N ^ 2), поскольку они проверяют каждый новый набор на все существующие, поэтому я использовал подход, который индексирует каждое число и работает на близком к O (N) (если мы принимаем, что поиск по словарю - O (1)). Затем я запустил тесты и почувствовал себя полным идиотом, потому что он работал медленнее, но при ближайшем рассмотрении оказалось, что тестовые данные заканчиваются только несколькими различными наборами результатов, поэтому квадратичные алгоритмы не имеют большой работы для делать. Протестируйте его более чем на 10-15 различных ящиков, и мой алгоритм выполняется намного быстрее. Попробуйте тестовые данные с более чем 50 отдельными ящиками, и это невероятно быстрее.

(Edit: Также была проблема с тем, как выполняется тест, но я был не прав в моем диагнозе. Я изменил свой код, чтобы работать с тем, как выполняются повторные тесты.)

def mergelists5(data):
    """Check each number in our arrays only once, merging when we find
    a number we have seen before.
    """

    bins = range(len(data))  # Initialize each bin[n] == n
    nums = dict()

    data = [set(m) for m in data ]  # Convert to sets    
    for r, row in enumerate(data):
        for num in row:
            if num not in nums:
                # New number: tag it with a pointer to this row's bin
                nums[num] = r
                continue
            else:
                dest = locatebin(bins, nums[num])
                if dest == r:
                    continue # already in the same bin

                if dest > r:
                    dest, r = r, dest   # always merge into the smallest bin

                data[dest].update(data[r]) 
                data[r] = None
                # Update our indices to reflect the move
                bins[r] = dest
                r = dest 

    # Filter out the empty bins
    have = [ m for m in data if m ]
    print len(have), "groups in result"
    return have


def locatebin(bins, n):
    """
    Find the bin where list n has ended up: Follow bin references until
    we find a bin that has not moved.
    """
    while bins[n] != n:
        n = bins[n]
    return n

Просто для удовольствия ...

def merge(mylists):
    results, sets = [], [set(lst) for lst in mylists if lst]
    upd, isd, pop = set.update, set.isdisjoint, sets.pop
    while sets:
        if not [upd(sets[0],pop(i)) for i in xrange(len(sets)-1,0,-1) if not isd(sets[0],sets[i])]:
            results.append(pop(0))
    return results

и моя переписка с лучшим ответом

def merge(lsts):
  sets = map(set,lsts)
  results = []
  while sets:
    first, rest = sets[0], sets[1:]
    merged = False
    sets = []
    for s in rest:
      if s and s.isdisjoint(first):
        sets.append(s)
      else:
        first |= s
        merged = True
    if merged: sets.append(first)
    else: results.append(first)
  return results

Мое решение хорошо работает в небольших списках и вполне читаемо без зависимостей.

def merge_list(starting_list):
    final_list = []
    for i,v in enumerate(starting_list[:-1]):
        if set(v)&set(starting_list[i+1]):
            starting_list[i+1].extend(list(set(v) - set(starting_list[i+1])))
        else:
            final_list.append(v)
    final_list.append(starting_list[-1])
    return final_list

Бенчмаркинг:

lists = [[1,2,3], [ 3,5,6], [8,9,10], [11,12,13]]

% timeit merge_list (lists)

100000 циклов, лучше всего 3: 4,9 мкс на петлю

Вот реализация, использующая структуру данных с разделенными наборами (в частности, дизъюнктный лес), благодаря подсказке putstorm в слияющих множествах, которые имеют хотя бы один элемент в общий . Я использую сжатие пути для улучшения скорости (~ 5%); это не совсем необходимо (и это предотвращает find хвостом рекурсивный, что может замедлить работу). Обратите внимание, что я использую dict для представления непересекающегося леса; учитывая, что данные int s, массив также работал бы, хотя это может быть не намного быстрее.

def merge(data):
    parents = {}
    def find(i):
        j = parents.get(i, i)
        if j == i:
            return i
        k = find(j)
        if k != j:
            parents[i] = k
        return k
    for l in filter(None, data):
        parents.update(dict.fromkeys(map(find, l), find(l[0])))
    merged = {}
    for k, v in parents.items():
        merged.setdefault(find(v), []).append(k)
    return merged.values()

Этот подход сопоставим с другими лучшими алгоритмами тестов Rik.

Это можно решить в O (n), используя алгоритм объединения-поиска. При первых двух строках ваших данных края, используемые в объединении-нахождении, следующие пары: (0,1), (1,3), (1,0), (0,3), (3,4 ), (4,5), (5,10)

Использование матричных манипуляций

Позвольте мне предисловие к этому ответу со следующим комментарием:

ЭТО НЕПРАВИЛЬНЫЙ СПОСОБ ДЕЛАТЬ ЭТО. ЭТО ПРЕДОТВРАТЬ НА ЧИСЛЕННУЮ НЕУСТОЙЧИВОСТЬ И БОЛЬШЕ СКОРОСТЬ, ЧТО ДРУГИЕ МЕТОДЫ ПРЕДСТАВЛЕНЫ, ИСПОЛЬЗУЮТСЯ НА ВАШЕМ СОБСТВЕННОМ РИСКЕ.

Сказанное, я не мог устоять перед решением проблемы с динамической точки зрения (и я надеюсь, вы получите свежий взгляд на проблему). В теории это должно работать все время, но вычисления собственных значений могут часто терпеть неудачу. Идея состоит в том, чтобы рассматривать ваш список как поток из строк в столбцы. Если две строки имеют общую ценность, между ними существует соединительный поток. Если бы мы думали об этих потоках как о воде, мы бы увидели, что потоки кластеризуются в маленькие пулы, когда между ними существует соединительный путь. Для простоты я собираюсь использовать меньший набор, хотя он также работает с вашим набором данных:

from numpy import where, newaxis
from scipy import linalg, array, zeros

X = [[0,1,3],[2],[3,1]]

Нам нужно преобразовать данные в потоковый граф. Если строка i втекает в значение j , поместим ее в матрицу. Здесь у нас есть 3 строки и 4 уникальных значения:

A = zeros((4,len(X)), dtype=float)
for i,row in enumerate(X):
    for val in row: A[val,i] = 1

В общем, вам нужно будет изменить 4, чтобы записать количество уникальных значений, которые у вас есть. Если набор представляет собой список целых чисел, начиная с 0, как у нас, вы можете просто сделать это самым большим числом. Теперь мы выполняем разложение по собственным значениям. SVD, если быть точным, поскольку наша матрица не является квадратной.

S  = linalg.svd(A)

Мы хотим сохранить только часть 3х3 этого ответа, поскольку она будет представлять поток пулов. На самом деле нам нужны только абсолютные значения этой матрицы; нам остается только, есть ли поток в этом пространстве cluster .

M  = abs(S[2])

Мы можем представить эту матрицу M как марковскую матрицу и сделать ее явной по нормировке строк. Как только мы это получим, мы вычисляем (слева) разложение собственного значения. этой матрицы.

M /=  M.sum(axis=1)[:,newaxis]
U,V = linalg.eig(M,left=True, right=False)
V = abs(V)

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

idx = where(U > .999)[0]
C = V.T[idx] > 0

Я должен использовать .999 из-за вышеупомянутой числовой неустойчивости. На этом мы закончили! Каждый независимый кластер может теперь вывести соответствующие строки:

for cluster in C:
    print where(A[:,cluster].sum(axis=1))[0]

Что дает, как и предполагалось:

[0 1 3]
[2]

Измените X на lst, и вы get: [ 0 1 3 4 5 10 11 16] [2 8].

Добавление

Почему это может быть полезно? Я не знаю, откуда берутся ваши базовые данные, но что происходит, когда соединения не являются абсолютными? У строки 1 есть запись 3 80% времени - как бы вы обобщили проблему? Метод потока выше работал бы очень хорошо и был бы полностью параметризован этим значением .999, чем дальше от единства, тем слабее ассоциация.

Визуальное представление

Поскольку изображение стоит 1K слов, вот графики матриц A и V для моего примера и ваши lst соответственно. Обратите внимание, как в V разбивается на два кластера (это блок-диагональная матрица с двумя блоками после перестановки), так как для каждого примера было только два уникальных списка!

[/g9] [/g10]

Быстрая реализация

Оглядываясь назад, я понял, что вы можете пропустить шаг SVD и вычислить только один decomp:

M = dot(A.T,A)
M /=  M.sum(axis=1)[:,newaxis]
U,V = linalg.eig(M,left=True, right=False)

Преимущество этого метода (помимо скорости) состоит в том, что M теперь является симметричным, поэтому вычисление может быть более быстрым и точным (никаких мнимых значений не беспокоить)

Это будет мой обновленный подход :

def merge(data):
    sets = (set(e) for e in data if e)
    results = [next(sets)]
    for e_set in sets:
        to_update = []
        for i,res in enumerate(results):
            if not e_set.isdisjoint(res):
                to_update.insert(0,i)

        if not to_update:
            results.append(e_set)
        else:
            last = results[to_update.pop(-1)]
            for i in to_update:
                last |= results[i]
                del results[i]
            last |= e_set

    return results

Примечание: во время слияния пустые списки будут удалены.

Обновление: Надежность.

Вам нужно два теста для 100% надежности успеха:

• Убедитесь, что все результирующие множества взаимно разделены:

  merged = [{0, 1, 3, 4, 5, 10, 11, 16}, {8, 2}, {8}]
  
  from itertools import combinations
  for a,b in combinations(merged,2):
      if not a.isdisjoint(b):
          raise Exception(a,b)    # just an example
  

• Убедитесь, что объединенный набор охватывает исходные данные. (как было предложено katrielalex)

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

Во-первых, я не совсем уверен, справедливы ли тесты:

Добавление следующего кода в начало моей функции:

c = Counter(chain(*lists))
    print c[1]
"88"

Это означает, что из всего значения во всех списках, есть только 88 различных значений. Обычно в реальном мире дубликаты встречаются редко, и вы ожидаете гораздо более отличных значений. (конечно, я не знаю, где ваши данные из этого не могут делать предположения).

Поскольку дубликаты чаще встречаются, это означает, что сеты менее вероятно, будут непересекающимися. Это означает, что метод set.isdisjoint () будет намного быстрее, потому что только после нескольких тестов он обнаружит, что наборы не пересекаются.

Сказав все это, я верю, что представленные методы, которые используют disjoint являются самыми быстрыми в любом случае, но я просто говорю, вместо того, чтобы быть в 20 раз быстрее, возможно, они должны быть только в 10 раз быстрее, чем другие методы с различным тестовым тестированием.

В любом случае, я думал, что попробую немного другой метод для решения этой проблемы, однако сортировка слияния была слишком медленной, этот метод примерно в 20 раз медленнее, чем два самых быстрых метода, использующих бенчмаркинг:

Я думал, что я закажу все

import heapq
from itertools import chain
def merge6(lists):
    for l in lists:
        l.sort()
    one_list = heapq.merge(*[zip(l,[i]*len(l)) for i,l in enumerate(lists)]) #iterating through one_list takes 25 seconds!!
    previous = one_list.next()

    d = {i:i for i in range(len(lists))}
    for current in one_list:
        if current[0]==previous[0]:
            d[current[1]] = d[previous[1]]
        previous=current

    groups=[[] for i in range(len(lists))]
    for k in d:
        groups[d[k]].append(lists[k]) #add a each list to its group

    return [set(chain(*g)) for g in groups if g] #since each subroup in each g is sorted, it would be faster to merge these subgroups removing duplicates along the way.


lists = [[1,2,3],[3,5,6],[8,9,10],[11,12,13]]
print merge6(lists)
"[set([1, 2, 3, 5, 6]), set([8, 9, 10]), set([11, 12, 13])]""



import timeit
print timeit.timeit("merge1(lsts)", setup=setup, number=10)
print timeit.timeit("merge4(lsts)", setup=setup, number=10)
print timeit.timeit("merge6(lsts)", setup=setup, number=10)
5000 lists, 5 classes, average size 74, max size 1000
1.26732238315
5000 lists, 5 classes, average size 74, max size 1000
1.16062907437
5000 lists, 5 classes, average size 74, max size 1000
30.7257182826

Вот функция (Python 3.1), чтобы проверить, является ли результат функции слияния ОК. Он проверяет:

• Являются ли результирующие множества непересекающимися? (количество элементов объединения == сумма чисел элементов)
• Являются ли элементы результата такими же, как и для входных списков?
• Является ли каждый список входных данных подмножеством результирующий набор?
• Является ли каждый результат минимальным, т. е. невозможно разбить его на два меньших множества?
• Он делает not проверить, есть ли пустые наборы результатов - я не знаю, хотите ли вы их или нет ...

.

from itertools import chain

def check(lsts, result):
    lsts = [set(s) for s in lsts]
    all_items = set(chain(*lsts))
    all_result_items = set(chain(*result))
    num_result_items = sum(len(s) for s in result)
    if num_result_items != len(all_result_items):
        print("Error: result sets overlap!")
        print(num_result_items, len(all_result_items))
        print(sorted(map(len, result)), sorted(map(len, lsts)))
    if all_items != all_result_items:
        print("Error: result doesn't match input lists!")
    if not all(any(set(s).issubset(t) for t in result) for s in lst):
        print("Error: not all input lists are contained in a result set!")

    seen = set()
    todo = list(filter(bool, lsts))
    done = False
    while not done:
        deletes = []
        for i, s in enumerate(todo): # intersection with seen, or with unseen result set, is OK
            if not s.isdisjoint(seen) or any(t.isdisjoint(seen) for t in result if not s.isdisjoint(t)):
                seen.update(s)
                deletes.append(i)
        for i in reversed(deletes):
            del todo[i]
        done = not deletes
    if todo:
        print("Error: A result set should be split into two or more parts!")
        print(todo)