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

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

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

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

если a == b и b == c, то a == c

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

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

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

Я думаю, что наиболее эффективным способом достижения этого будет использование 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: 10.049749890022213

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

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

 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 

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

Время заполонить руки

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

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

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

Непересекающееся множество фактически является своего рода древовидной структурой. Давайте рассмотрим каждое число как узел дерева, и каждый раз, когда мы читаем в ребро (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 (родительский или корневой). В частности, предком узла узла с одним узлом является сам.

Interesting Posts