Создать список уникальных номеров, применяя транзитивное замыкание

Question

У меня есть список кортежей (каждый кортеж состоит из 2-х номеров), как:

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

Давайте говорить, что эти цифры являются идентификаторами некоторых объектов БД (записей) и внутри кортежа есть идентификаторы повторяющихся объектов. Это означает, что 1 и 2 дублируются. 1 и 3 являются дубликатами, что означает, что 2 и 3 также являются дублирующими.

если == Ь и Ь == с тогда == с

Теперь я хочу, чтобы объединить все эти повторяющиеся объекты идентификаторы в один кортеж, как это:

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

Я знаю, что могу сделать это, используя циклы и избыточные совпадения. Я просто хочу лучшее решение с низкой обработкой/вычислениями (если таковые имеются).

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 

Sample пробег:

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

• Willem's solution: 29,115453064994654 (время, связанные с декларацией класса исключается)

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

• hsfzxjy's solution: 10.049749890022213

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

Answer 2

Вы можете использовать непересекающийся набор.

Disjoint set на самом деле своего рода древовидная структура. Рассмотрим каждый номер как узел дерева, и каждый раз, когда мы читаем в ребро (u, v), мы просто связываем два дерева u и v (если оно не существует, вместо него создайте одноузловое дерево), указав корневой узел одного дерева в чужое. В конце мы должны просто пройтись по лесу, чтобы получить результат.

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] хранит предка узла u (родитель или корень). В частности, предком узла узла с одним узлом является сам.

Answer 3

Вы можете использовать структуру данных, что делает ее более эффективной для выполнения слияния. Здесь вы создаете нечто вроде противоположного дерева. Таким образом, в вашем примере вы сначала создали бы число перечисленных:

1 2 3 4 5 8 10 

Теперь, если вы перебрать (1,2) кортежа, вы смотрите 1 и 2 в каком-то словаре. Ищешь их предков (их нет здесь), а затем вы создаете какой-то слияния узла:

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 

Вы также сохраняете список «слитных головок», чтобы вы могли легко вернуть элементы.

Времени, чтобы получить в свои руки грязные

Так что теперь мы знаем, как построить такую ​​структуру данных, давайте реализуем один.Сначала определим узел:

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()) 

Теперь для каждого кортежа в массиве, мы LookUp соответствующего 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) 

Наконец после того, как мы сделали, что мы можем просто построить 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 (log n) вместо этого, делая его O (n log n). Кроме того, вы можете короткое замыкание список предков, что делает его еще быстрее.