Объединение множеств в списке на основе их пересечения

Question

Существует некоторый большой список, содержащий в себе множества. В качестве примера возьмем такой вид:

a = [{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 20}, {5, 9}, {1, 8}].

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

a = [{0, 1, 2, 3, 8, 20}, {4, 5, 6, 7, 9}]

Пробовал следующий способ:

a = [{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 20}, {5, 9}, {1, 8}]
new = []
for _i in range(len(a)):
    tmp = a[_i]
    for _j in range(len(a)):
        if tmp.isdisjoint(a[_j]) == False:
            tmp = tmp.union(a[_j])
    new.append(tmp)
test = []
for _i in new:
    if _i not in test:
        test.append(_i)
print(test)

Но он оказался: во-первых, слишком медленным, а во-вторых он не учитывает ситуацию, когда множество1 имеет пересечение с множеством2, а множество2 имеет пересечение с множеством3 и так далее, так что он выдает результат:

[{0, 1, 2, 3, 8}, {4, 5, 6, 7, 9}, {8, 1, 20}, {0, 1, 2, 3, 20, 8}]

Тестировал на списке из 800 тысяч множеств, ожидаемое время обработки оказалось 24 часа.

Answer 1

Вот вроде получилось. Наверняка через itertools можно как-то проще сделать, но так вроде работает.

def flatten_setlist(old):
  new = []
  # идем по списку set-ов
  for o in old:
    found = False
    # если новый список пока пустой, то добавляем туда set без всяких проверок
    if len(new) == 0:
      new.append(o)
      continue
    # перебираем set-ы из нового списка
    for n in new:
      # если есть пересечение
      if len(n & o) > 0:
        found = True
        # то добавляем set в имеющийся set
        n |= o
        break
    # если не найдено ни одного пересечения с сетами из нового списка, то добавляем set в список новых set-ов
    if(not found):
      new.append(o)
  return new

old = [{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 20}, {5, 9}, {1, 8}]
# процесс "схлопывания" списка сходится не сразу, поэтому нужен ещё один цикл
while True:
  new = flatten_setlist(old)
  # если работа алгоритма не привела к изменениям в списке, то работу цикла прекращаем
  if(len(new) == len(old)):
    break
  old = new

print(new)

UPDATE: Сделал некоторую оптимизацию, попробуйте. Должна хорошо ускорить, если у вас часто перебираемые наборы не попадают в уже имеющиеся наборы. Но вообще tqdm лучше выкинуть, он красивый, конечно, но замедляет процессы во много раз.

from tqdm import tqdm_notebook

def flatten_setlist(old):
  print('old list len = ', len(old))
  # процесс "схлопывания" списка сходится не сразу, поэтому нужен ещё один цикл
  with tqdm_notebook(total=len(old)) as pbar:
    while True:
      new = []
      new_all = set()
      # идем по списку set-ов
      for o in tqdm_notebook(old, leave=False):
        #found = False
        # если новый список пока пустой, то добавляем туда set без всяких проверок
        if len(new) == 0:
          new.append(o)
          new_all |= o
          continue
        if len(new_all & o) > 0:
          # перебираем set-ы из нового списка
          for n in new:
            # если есть пересечение
            if len(n & o) > 0:
              #found = True
              # то добавляем set в имеющийся set
              n |= o
              new_all |= o
              break
        else:
          # если не найдено ни одного пересечения с сетами из нового списка, то добавляем set в список новых set-ов
          new.append(o)
          new_all |= o
      # если работа алгоритма не привела к изменениям в списке, то работу цикла прекращаем
      if(len(new) == len(old)):
        print('new list len = ', len(new))
        return new
      pbar.update(len(old)-len(new))
      old = new

old = [{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 20}, {5, 9}, {1, 8}]
print(flatten_setlist(old))

БЛОГ НА HUSL

Объединение множеств в списке на основе их пересечения

Ответы (1 шт):