Create a list of unique numbers using transitive closure

Question

I have a list of tuples (each set consists of two numbers), for example:

array = [(1, 2), (1, 3), (2, 4), (5, 8), (8, 10)]

Suppose that these numbers are identifiers of some db objects (records) and inside the tuple, there are identifiers of duplicated objects. This means that 1 and 2 are duplicated. 1 and 3 are duplicates, which mean 2 and 3, are also duplicates.

if a == b and b == c, then a == c

Now I want to merge all these duplicate objects into one tuple as follows:

output = [(1, 2, 3, 4), (5, 8, 10)]

I know I can do this using loops and redundant matches. I just want a better solution with low processing / computation (if any).

Answer 1

, set :

def transitive_cloure(array):
    new_list = [set(array.pop(0))]  # initialize first set with value of index `0`

    for item in array:
        for i, s in enumerate(new_list):
            if any(x in s for x in item):
                new_list[i] = new_list[i].union(item)
                break
        else:
            new_list.append(set(item))
    return new_list

:

>>> transitive_cloure([(1,2), (1,3), (2,4), (5,8), (8,10)])
[{1, 2, 3, 4}, {8, 10, 5}]

---

( Python 3.4):

• : 6.238126921001822

  >>> timeit.timeit("moin()", setup="from __main__ import moin")
  6.238126921001822
  

• : 29.115453064994654 ( , )

  >>> timeit.timeit("willem()", setup="from __main__ import willem")
  29.115453064994654
  

• hsfzxjy solution: 10.049749890022213

  >>> timeit.timeit("hsfzxjy()", setup="from __main__ import hsfzxjy")
  10.049749890022213
  

Answer 2

, . . , :

1  2  3  4  5  8  10

, (1,2), 1 2 - . ( ), - node:

1  2  3  4  5  8  10
 \/
 12

(1,3), 1 (12) 3 (3) :

1  2  3  4  5  8  10
 \/   |
 12  /
   \/
  123

(2,4) (5,8) (8,10):

1  2  3  4  5  8  10
 \/   |  |   \/   |
 12  /   |   58  /
   \/   /      \/
  123  /      5810
     \/
    1234

" ", .

, , , ​​ , . a node:

class Merge:

    def __init__(self,value=None,parent=None,subs=()):
        self.value = value
        self.parent = parent
        self.subs = subs

    def get_ancestor(self):
        cur = self
        while cur.parent is not None:
            cur = cur.parent
        return cur

    def __iter__(self):
        if self.value is not None:
            yield self.value
        elif self.subs:
            for sub in self.subs:
                for val in sub:
                    yield val

:

vals = set(x for tup in array for x in tup)

vals, Merge:

dic = {val:Merge(val) for val in vals}

merge_heads:

merge_heads = set(dic.values())

Merge, , Merge, merge_head Merge :

for frm,to in array:
    mra = dic[frm].get_ancestor()
    mrb = dic[to].get_ancestor()
    mr = Merge(subs=(mra,mrb))
    mra.parent = mr
    mrb.parent = mr
    merge_heads.remove(mra)
    merge_heads.remove(mrb)
    merge_heads.add(mr)

, , , a set Merge merge_heads:

resulting_sets = [set(merge) for merge in merge_heads]

resulting_sets ( ):

[{1, 2, 3, 4}, {8, 10, 5}]

( class):

vals = set(x for tup in array for x in tup)
dic = {val:Merge(val) for val in vals}
merge_heads = set(dic.values())
for frm,to in array:
    mra = dic[frm].get_ancestor()
    mrb = dic[to].get_ancestor()
    mr = Merge(subs=(mra,mrb))
    mra.parent = mr
    mrb.parent = mr
    merge_heads.remove(mra)
    merge_heads.remove(mrb)
    merge_heads.add(mr)
resulting_sets = [set(merge) for merge in merge_heads]

, O (n ²), , O (log n), O (n log n), , , .

Answer 3

.

Disjoint set . node, , (u, v), u v in ( , - w631 > tree), node . , .

from collections import defaultdict


def relation(array):

    mapping = {}

    def parent(u):
        if mapping[u] == u:
            return u
        mapping[u] = parent(mapping[u])
        return mapping[u]

    for u, v in array:
        if u not in mapping:
            mapping[u] = u
        if v not in mapping:
            mapping[v] = v
        mapping[parent(u)] = parent(v)

    results = defaultdict(set)

    for u in mapping.keys():
        results[parent(u)].add(u)

    return [tuple(x) for x in results.values()]

mapping[u] node u ( ). , node node .