There is a list of equals , which contains several sets. I need all intersecting sets in this list to merge into one.

Example:

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 2

    You can use the brute force method and combine sets recursively:

     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

    Example :

     >>> 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}] 

     <script src="https://cdn.rawgit.com/brython-dev/brython/3.4.0/www/src/brython.js"></script><body onload="brython()"><script type="text/python"> def condense_sets(sets): result = [] for candidate in sets: for current in result: if candidate & current: # found overlap current.update(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 # try your own input import json from browser import document @document["mybutton"].bind("click") def on_click(event): sets = list(map(set, json.loads(document["json"].text))) print(condense_sets(sets)) </script><label for="json">JSON ввод: </label><span id="json" contenteditable="true">[[1,2], [2,3], [3,4], [10, 11, 12], [10, 13], [20, 21]]</span> <button id="mybutton">Запустить</button></body>

    This and more efficient algorithms based on the disjoint set system, union-find system or connected graph component (connected components) can be found in solutions of a similar, but somewhat different problem: Replace list list list with "condensed" list of list while maintaining order .

       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}]