Я видел только решения, которые делают несколько проходов по sets (обычно O(N^2)). Итак, из любопытства я хотел посмотреть, можно ли это сделать только с одним проходом по sets (т.е. O(N)).
Используя входной набор из исходного вопроса, вот пример того, как этот алгоритм перебирает каждый набор в списке.
[
set([1,3]), # A
set([2,3,5]), # B
set([21,22]), # C
set([1,9]), # D
set([5]), # E
set([18,21]), # F
]
Мы начинаем с набора A (set([1,3])) и предполагаем, что он является частью нового списка результатов L1. Мы также поддерживаем указатель C1 на наш текущий список результатов (в данный момент это L1). Назначение этого указателя будет объяснено позже:
L1 = [set([1,3]),]
C1 = Pointer(L1)
Для каждого целого числа в наборе A мы также обновляем наше отображение M:
{
1: C1, # Pointer(L1)
3: C1, # Pointer(L1)
}
Следующий элемент — набор B (set([2,3,5])), и мы предполагаем, что он является частью нового списка результатов L2.
L2 = [set([2,3,5]),]
C2 = Pointer(L2)
Опять же, мы повторяем элементы этого набора и обновляем наше отображение M. В явном виде мы видим, что 2 не находится в M, и мы обновляем его таким образом, что у нас есть:
{
1: C1, # Pointer(L1)
3: C1, # Pointer(L1)
2: C2, # Pointer(L2)
}
Однако, когда мы видим 3, мы замечаем, что он уже указывает на другой список результатов, L1. Это указывает на наличие пересечения, и нам нужно сделать две вещи:
- Обновите C2, чтобы он указывал на L1
- Добавить набор B в L1
У нас должно получиться, что М выглядит так:
{
1: C1, # Pointer(L1)
3: C1, # Pointer(L1)
2: C2, # Pointer(L1)
}
И L1 теперь должен быть:
[[set([1,3]), set([2,3,5])]
Вот почему нам нужен класс Pointer: мы не можем просто присвоить C2 новому экземпляру Pointer(). Если мы это сделаем, то М будет выглядеть так:
{
1: C1, # Pointer(L1)
3: C1, # Pointer(L1)
2: C2, # Pointer(L2) <-- this should be pointing to L1
}
Вместо этого мы делаем что-то вроде:
C2.set(L1)
Забегая вперед, после того, как мы обработали набор B и набор C, состояние M должно выглядеть так:
{
1: C1, # Pointer(L1)
3: C1, # Pointer(L1)
2: C2, # Pointer(L1)
5: C2, # Pointer(L1)
21: C3, # Pointer(L3)
22: C3, # Pointer(L3)
}
И список результатов:
[set([1,3]), set([2,3,5])] # L1
[set([21,22]), ] # L3
[set([2,3,5]), ] # L2 (but nothing in M points to it)
Когда мы смотрим на набор D, мы снова предполагаем, что он является частью нового списка результатов, L4, и создаем соответствующий указатель, C4, который указывает на L4. Однако, когда мы видим, что набор D содержит 1, который пересекается с L1, мы меняем C4, чтобы он указывал на L1, и добавляем набор D к L1.
Состояние М:
{
1: C1, # Pointer(L1)
3: C1, # Pointer(L1)
2: C2, # Pointer(L1)
5: C2, # Pointer(L1)
21: C3, # Pointer(L3)
22: C3, # Pointer(L3)
9: C4, # Pointer(L1)
}
И L1 сейчас:
[set([1,3]), set([2,3,5]), set([1,9])]
Пройдя весь путь до конца, состояние M будет выглядеть так:
{
1: C1, # Pointer(L1)
3: C1, # Pointer(L1)
2: C2, # Pointer(L1)
5: C2, # Pointer(L1)
21: C3, # Pointer(L3)
22: C3, # Pointer(L3)
9: C4, # Pointer(L1)
18: C6, # Pointer(L3)
}
И списки выглядят так:
[set([1,3]), set([2,3,5]), set([1,9]), set([5])] # L1
[set([21,22]), set([18, 21]) # L3
На этом этапе вы можете перебрать указатели в M и найти все уникальные списки, на которые ссылаются, и это будет ваш результат.
В исходном коде я пытался избежать этого последнего шага, поддерживая список уникальных наборов результатов на лету. Но я удалил эту логику, чтобы упростить код, поскольку прирост производительности, вероятно, в любом случае не так уж велик.
Вот обновленный код с исправлением ошибки, упомянутой Андреа в комментариях.
class Pointer(object):
"""
Implements a pointer to an object. The actual object can be accessed
through self.get().
"""
def __init__(self, o): self.o = o
def __str__(self): return self.o.__str__()
def __repr__(self): return '<Pointer to %s>' % id(self.o)
# These two methods make instances hashed on self.o rather than self
# so Pointers to the same object will be considered the same in
# dicts, sets, etc.
def __eq__(self, x): return x.o is self.o
def __hash__(self): return id(self.o)
def get(self): return self.o
def set(self, obj): self.o = obj.o
def id(self): return id(self.o)
def connected_sets(s):
M = {}
for C in s:
# We assume C belongs to a new result list
P = Pointer(list())
added = False # to check if we've already added C to a result list
for item in C:
# There was an intersection detected, so the P points to this
# intersecting set. Also add this C to the intersecting set.
if item in M:
# The two pointers point to different objects.
if P.id() != M[item].id():
# If this was a regular assignment of a set to a new set, this
# wouldn't work since references to the old set would not be
# updated.
P.set(M[item])
M[item].o.append(C)
added = True
# Otherwise, we can add it to P which, at this point, could point to
# a stand-alone set or an intersecting set.
else:
if not added:
P.o.append(C)
added = True
M[item] = P
return M
if __name__ == '__main__':
sets = [
set([1,3]), # A
set([2,3,5]), # B
set([21,22]), # C
set([1,9]), # D
set([5]), # E
set([18,21]), # F
]
#sets = [
# set([1,5]), # A
# set([1,5]), # B
#]
M = connected_sets(sets)
import pprint
pprint.pprint(
# create list of unique lists referenced in M
[x.o for x in set(M.values())]
)
И вывод для:
[[set([1, 3]), set([2, 3, 5]), set([1, 9]), set([5])],
[set([21, 22]), set([18, 21])]]
Кажется, это работает для меня, но мне было бы любопытно, как это работает по сравнению с вашим решением. Используя модуль timeit, я сравнил это с ответом выше, в котором используется networkx, и мой скрипт почти в 3 раза быстрее на том же наборе данных.
15.07.2014
