13

所以这就是我想要做的：我有一个包含几个等价关系的列表：

l = [[1, 2], [2, 3], [4, 5], [6, 7], [1, 7]]

我想合并共享一个元素的集合。这是一个示例实现：

def union(lis):
  lis = [set(e) for e in lis]
  res = []
  while True:
    for i in range(len(lis)):
      a = lis[i]
      if res == []:
        res.append(a)
      else:
        pointer = 0 
        while pointer < len(res):
          if a & res[pointer] != set([]) :
            res[pointer] = res[pointer].union(a)
            break
          pointer +=1
        if pointer == len(res):
          res.append(a)
     if res == lis:
      break
    lis,res = res,[]
  return res

它打印

[set([1, 2, 3, 6, 7]), set([4, 5])]

这是正确的，但当等价关系太大时，速度太慢了。我查看了关于联合查找算法的描述：http ://en.wikipedia.org/wiki/Disjoint-set_data_structure 但我仍然在编写 Python 实现时遇到问题。

4

4 回答 4

10

O(n)及时运行的解决方案

def indices_dict(lis):
    d = defaultdict(list)
    for i,(a,b) in enumerate(lis):
        d[a].append(i)
        d[b].append(i)
    return d

def disjoint_indices(lis):
    d = indices_dict(lis)
    sets = []
    while len(d):
        que = set(d.popitem()[1])
        ind = set()
        while len(que):
            ind |= que 
            que = set([y for i in que 
                         for x in lis[i] 
                         for y in d.pop(x, [])]) - ind
        sets += [ind]
    return sets

def disjoint_sets(lis):
    return [set([x for i in s for x in lis[i]]) for s in disjoint_indices(lis)]

这个怎么运作：

>>> lis = [(1,2),(2,3),(4,5),(6,7),(1,7)]
>>> indices_dict(lis)
>>> {1: [0, 4], 2: [0, 1], 3: [1], 4: [2], 5: [2], 6: [3], 7: [3, 4]})

indices_dict给出从等价 # 到 . 中的索引的映射lis。例如1映射到 index0和4in lis。

>>> disjoint_indices(lis)
>>> [set([0,1,3,4], set([2])]

disjoint_indices给出不相交的索引集的列表. 每个集合对应于等价中的索引。例如lis[0]和lis[3]是相同的等价物，但不是lis[2]。

>>> disjoint_set(lis)
>>> [set([1, 2, 3, 6, 7]), set([4, 5])]

disjoint_set将不相交的索引转换为其适当的等价物。

时间复杂度

时间复杂度很难看，O(n)但我会尝试解释。在这里我将使用n = len(lis).

  1. indices_dict肯定会O(n)及时运行，因为只有 1 个 for 循环

  2. disjoint_indices是最难看到的。它肯定会O(len(d))及时运行，因为外部循环在为空时停止d并且内部循环删除d每次迭代的一个元素。现在，len(d) <= 2nsinced是从等价 # 到索引的映射，并且在 中最多有2n不同的等价 # lis。因此，函数在O(n).

  3. disjoint_sets由于 3 个组合的 for 循环，很难看到。但是，您会注意到最多i可以遍历所有n索引lis并x遍历 2 元组，因此总复杂度为2n = O(n)

于 2013-11-23T20:08:55.147 回答
5

我认为这是一个优雅的解决方案，使用内置的 set 函数：

#!/usr/bin/python3

def union_find(lis):
    lis = map(set, lis)
    unions = []
    for item in lis:
        temp = []
        for s in unions:
            if not s.isdisjoint(item):
                item = s.union(item)
            else:
                temp.append(s)
        temp.append(item)
        unions = temp
    return unions



if __name__ == '__main__':
    l = [[1, 2], [2, 3], [4, 5], [6, 7], [1, 7]]
    print(union_find(l))

它返回一个集合列表。

于 2013-11-22T22:30:20.853 回答
0

也许是这样的？

#!/usr/local/cpython-3.3/bin/python

import copy
import pprint
import collections

def union(list_):
    dict_ = collections.defaultdict(set)

    for sublist in list_:
        dict_[sublist[0]].add(sublist[1])
        dict_[sublist[1]].add(sublist[0])

    change_made = True
    while change_made:
        change_made = False
        for key, values in dict_.items():
            for value in copy.copy(values):
                for element in dict_[value]:
                    if element not in dict_[key]:
                        dict_[key].add(element)
                        change_made = True

    return dict_

list_ = [ [1, 2], [2, 3], [4, 5], [6, 7], [1, 7] ]
pprint.pprint(union(list_))
于 2013-11-22T21:51:04.327 回答
0

这是通过一次完全耗尽一个等价物来实现的。当一个元素找到它的等价物时，它将从原始集合中删除并且不再搜索。

def equiv_sets(lis):
    s = set(lis)
    sets = []

    #loop while there are still items in original set
    while len(s):
        s1 = set(s.pop())
        length = 0
        #loop while there are still equivalences to s1
        while( len(s1) != length):
            length = len(s1)
            for v in list(s):
                if v[0] in s1 or v[1] in s1:
                    s1 |= set(v)
                    s  -= set([v])
        sets += [s1]
    return sets

print equiv_sets([(1,2),(2,3),(4,5),(6,7),(1,7)])

输出： [set([1, 2, 3, 6, 7]), set([4, 5])]

于 2013-11-22T22:32:20.110 回答