В списке множеств объединить пересекающиеся множества

208 просмотра
0

Есть список equals, в котором содержится несколько множеств. Мне нужно, чтобы все пересекающиеся множества в этом списке объединились в одно.

Пример:

equals = [ {1,2}, {2,3}, {3,4}, {10, 11, 12}, {10, 13}, {20, 21} ]
result = foo(equals)   # foo - та функция, которую мне нужно реализовать
print(result)          # Вывод: [{1, 2, 3, 4}, {10, 11, 12, 13}, {20, 21}]


Добавить комментарий

2 Answers

Python Опубликовано 14.12.2018
0

def merge_all_intersections(list_of_sets):
    if len(list_of_sets) > 1:
        start_index = len(list_of_sets) - 2
        while start_index != -1:
            for current_index in range(len(list_of_sets) - 1, start_index, -1):
                if list_of_sets[start_index].intersection(list_of_sets[current_index]):
                    list_of_sets[start_index] = list_of_sets[start_index].union(list_of_sets[current_index])
                    list_of_sets.pop(current_index)
            start_index -= 1
    return None
 
equals = [ {1, 2}, {2, 3}, {3, 4}, {10, 11, 12}, {10, 13}, {20, 21} ]
merge_all_intersections(equals)
print(equals)
# [{1, 2, 3, 4}, {10, 11, 12, 13}, {20, 21}]

Добавить комментарий
0

Можно воспользоваться методом грубой силы и рекурсивно объединять наборы:

def condense_sets(sets):
    result = []
    for candidate in sets:
        for current in result:
            if candidate & current:   # found overlap
                current |= candidate  # combine (merge sets)
 
                # new items from candidate may create an overlap
                # between current set and the remaining result sets
                result = condense_sets(result) # merge such sets
                break
        else:  # no common elements found (or result is empty)
            result.append(candidate)
    return result

Пример:

>>> sets = [ {1,2}, {2,3}, {3,4}, {10, 11, 12}, {10, 13}, {20, 21} ]
>>> condense_sets(sets)
[{1, 2, 3, 4}, {10, 11, 12, 13}, {20, 21}]
[[1,2], [2,3], [3,4], [10, 11, 12], [10, 13], [20, 21]] 

[/apcode]

Этот и более эффективные алгоритмы на основе cистемы непересекающихся множеств (disjoint set, union-find) или компонент связности графа (connected components) см. в решениях похожой, но несколько другой задачи: Replace list of list with "condensed" list of list while maintaining order.

Добавить комментарий
Напишите свой ответ на данный вопрос.
Scroll Up