Как, используя Python, объединить списки при совпадении хотя бы одного значения?

Question

[chonduhvan]

На входе есть сет уникальных коллекций идентификаторов. Нужно объединить их так, чтобы один идентификатор был только в одной коллекции. Внутри коллекции все идентификаторы уникальны. Внутри сета все коллекции уникальны. Размер сета достаточно большой (20000+), по-этому скорость имеет значение. Нужно решение на Python.
Пример:

changeset = set([               
   frozenset([101,102]),        
   frozenset([103,104]),        
   frozenset([101,105]),        
   frozenset([106,107,109,103]),
   frozenset([110,135]),        
   frozenset([111,136]), ])

На выходе должно получиться.

changeset = set([               
   frozenset([101,102,105]),        
   frozenset([103,104,106,107,109]),
   frozenset([110,135]),        
   frozenset([111,136]), ])

Comments

[Валентин]

А что будет, если в первом варианте добавить множество
frozenset([110, 104, 106, 135, 118])?

[chonduhvan]

В практической задаче таких ситуаций не возникает, но давайте допустим, что это возможно. В результате один идентификатор может присутствовать только в одной коллекции, т.е в нашем случае на выходе должно быть:
frozenset([101,102,105]),
frozenset([103,104,106,107,109,110,135,118]),
frozenset([111,136]),

Answer 1

[0re1]

За O(N * log(n)), где n - число уникальных идентификаторов, N - сумма мощностей множеств.

Система непересекающихся множеств:

def union(superset):
    parent = {}
    
    def make_set(a):
        if a not in parent: parent[a] = a
    
    def find_set(a):
        if parent[a] == a: return a
        parent[a] = find_set(parent[a])
        return parent[a]
        
    def union_sets(a, b):
        a = find_set(a)
        b = find_set(b)
        if a != b: parent[a] = b
    
    for subset in superset:
        prev = None
        for v in subset:
            make_set(v)
            if prev: union_sets(prev, v)
            prev = v

    lists = {}
    for uid in parent.keys():
        pr = find_set(uid)
        if pr not in lists: lists[pr] = []
        lists[pr].append(uid)

    return set([ frozenset(l) for l in lists.values() ])

>> union(changeset)
{frozenset({111, 136}),
 frozenset({101, 102, 105}),
 frozenset({110, 135}),
 frozenset({103, 104, 106, 107, 109})}

Answer 2

[mrstrictly]

Извините, я не Python разработчик. Ниже -- моё решение в лоб, которое возможно натолкнет на думы об оптимизации. :)

def join_intersections(aSet):
    aSetCopy = aSet.copy()
    for l, r in [[l,r] for l in changeset for r in changeset]:
        if not l.isdisjoint(r) and l != r:
            aSetCopy.discard(l)
            aSetCopy.discard(r)
            yield l | r
    for rest in aSetCopy:
        yield rest

>>> target_changeset = set(join_intersections(changeset))
>>> target_changeset
set([frozenset([136, 111]), frozenset([105, 101, 102]), frozenset([110, 135]), frozenset([103, 104, 106, 107, 109])])

Comments

[0re1]

Неверно, строит объединения лишь пар, пример:

>>changeset = set([
frozenset([101,102]),
frozenset([101,103]),
frozenset([101,104]),
])
>>set(join_intersections(changeset))
{frozenset({101, 102, 103}),
frozenset({101, 102, 104}),
frozenset({101, 103, 104})}