通过应用传递闭包创建唯一数字列表
Create a list of unique numbers by applying transitive closure
我有一个元组列表（每个元组包含 2 个数字），例如：
array = [(1, 2), (1, 3), (2, 4), (5, 8), (8, 10)]
比方说，这些数字是一些数据库对象（记录）的 ID，在一个元组中，有重复对象的 ID。这意味着 1 和 2 是重复的。 1 和 3 是重复的，这意味着 2 和 3 也是重复的。
if a == b and b == c then a == c
现在我想像这样将所有这些重复的对象 ID 合并到一个元组中：
output = [(1, 2, 3, 4), (5, 8, 10)]
我知道我可以使用循环和冗余匹配来做到这一点。我只是想要一些处理/计算较少的更好的解决方案（如果有的话）。
您可以使用不相交集。
不相交集实际上是一种树结构。让我们把每个数字看成一个树节点，每次读入一条边(u, v)，我们就很容易将两棵树u和v关联起来（如果不存在，创建one-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] 存储节点 u 的祖先（父节点或根节点）。特别地，one-node树节点的祖先是它自己。
您可以使用一种数据结构来更有效地执行合并。在这里你创建某种相反的树。因此，在您的示例中，您首先将创建列出的数字：
1 2 3 4 5 8 10
现在，如果您遍历 (1,2) 元组，您会在某种字典中查找 1 和 2。您搜索他们的祖先（这里有 none），然后创建某种 合并节点 :
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" 列表，因此您可以轻松 return 元素。
是时候亲自动手了
现在我们知道了如何构建这样的数据结构，让我们来实现一个。首先我们定义一个节点：
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)
最后，在我们完成之后，我们可以简单地为 merge_heads 中的每个 Merge 构造一个 set:
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(n2) 中的最坏情况 运行，但您可以 平衡 树使得在 O(log n) 中找到祖先，使其成为 O(n log n)。此外，您可以 short-circuit 祖先列表，使其更快。
我认为最有效的方法是使用 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 （不包括与class声明相关的时间）
>>> timeit.timeit("willem()", setup="from __main__ import willem")
29.115453064994654
: 10.049749890022213
>>> timeit.timeit("hsfzxjy()", setup="from __main__ import hsfzxjy")
10.049749890022213
请参阅我对 Moinuddin 回答的评论：此已接受的回答并未验证您可以在 http://rosettacode.org/wiki/Set_consolidation#Python 找到的测试。虽然我没有挖掘它。
我会根据Willem 的回答提出一个新的命题。
这个命题中的问题是 get_ancestor 调用中的递归性：为什么我们要爬树 每次 我们被问到我们的祖先时，我们只能记住最后一个根发现（并且仍然从那个点爬上以防它发生变化）。事实上，Willem 的算法不是线性的（类似于 nlogn 或 n²），而我们可以很容易地消除这种非线性。
另一个问题来自迭代器：如果树太深（我在用例中遇到了问题），您会在迭代器中得到一个 Python 异常（太多递归）。因此，我们应该合并子叶子而不是构建完整的树（并且我们构建具有 N 个叶子的分支而不是具有 2 个叶子的分支）。
我的代码版本如下：
class Merge:
def __init__(self,value=None,parent=None,subs=None):
self.value = value
self.parent = parent
self.subs = subs
self.root = None
if self.subs:
subs_a,subs_b = self.subs
if subs_a.subs:
subs_a = subs_a.subs
else:
subs_a = [subs_a]
if subs_b.subs:
subs_b = subs_b.subs
else:
subs_b = [subs_b]
self.subs = subs_a+subs_b
for s in self.subs:
s.parent = self
s.root = None
def get_ancestor(self):
cur = self if self.root is None else self.root
while cur.parent is not None:
cur = cur.parent
if cur != self:
self.root = cur
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
def treeconsolidate(array):
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 settomerge in array:
frm = settomerge.pop()
for to in settomerge:
mra = dic[frm].get_ancestor()
mrb = dic[to].get_ancestor()
if mra == mrb:
continue
mr = Merge(subs=[mra,mrb])
merge_heads.remove(mra)
merge_heads.remove(mrb)
merge_heads.add(mr)
resulting_sets = [set(merge) for merge in merge_heads]
return resulting_sets
在小型合并中，这不会改变很多事情，但我的经验表明，在包含许多元素的巨大集合中爬上树会花费很多：在我的例子中，我必须处理 100k 个集合，每个集合包含 2 到 1000 个元素，每个元素可能出现在 1 到 1000 个集合中...
我有一个元组列表（每个元组包含 2 个数字），例如：
array = [(1, 2), (1, 3), (2, 4), (5, 8), (8, 10)]
比方说，这些数字是一些数据库对象（记录）的 ID，在一个元组中，有重复对象的 ID。这意味着 1 和 2 是重复的。 1 和 3 是重复的，这意味着 2 和 3 也是重复的。
if a == b and b == c then a == c
现在我想像这样将所有这些重复的对象 ID 合并到一个元组中：
output = [(1, 2, 3, 4), (5, 8, 10)]
我知道我可以使用循环和冗余匹配来做到这一点。我只是想要一些处理/计算较少的更好的解决方案（如果有的话）。
您可以使用不相交集。
不相交集实际上是一种树结构。让我们把每个数字看成一个树节点，每次读入一条边(u, v)，我们就很容易将两棵树u和v关联起来（如果不存在，创建one-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] 存储节点 u 的祖先（父节点或根节点）。特别地，one-node树节点的祖先是它自己。
您可以使用一种数据结构来更有效地执行合并。在这里你创建某种相反的树。因此，在您的示例中，您首先将创建列出的数字：
1 2 3 4 5 8 10
现在，如果您遍历 (1,2) 元组，您会在某种字典中查找 1 和 2。您搜索他们的祖先（这里有 none），然后创建某种 合并节点 :
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" 列表，因此您可以轻松 return 元素。
是时候亲自动手了
现在我们知道了如何构建这样的数据结构，让我们来实现一个。首先我们定义一个节点：
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)
最后，在我们完成之后，我们可以简单地为 merge_heads 中的每个 Merge 构造一个 set:
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(n2) 中的最坏情况 运行，但您可以 平衡 树使得在 O(log n) 中找到祖先，使其成为 O(n log n)。此外，您可以 short-circuit 祖先列表，使其更快。
我认为最有效的方法是使用 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>>> timeit.timeit("willem()", setup="from __main__ import willem") 29.115453064994654>>> timeit.timeit("hsfzxjy()", setup="from __main__ import hsfzxjy") 10.049749890022213
请参阅我对 Moinuddin 回答的评论：此已接受的回答并未验证您可以在 http://rosettacode.org/wiki/Set_consolidation#Python 找到的测试。虽然我没有挖掘它。
我会根据Willem 的回答提出一个新的命题。 这个命题中的问题是 get_ancestor 调用中的递归性：为什么我们要爬树 每次 我们被问到我们的祖先时，我们只能记住最后一个根发现（并且仍然从那个点爬上以防它发生变化）。事实上，Willem 的算法不是线性的（类似于 nlogn 或 n²），而我们可以很容易地消除这种非线性。
另一个问题来自迭代器：如果树太深（我在用例中遇到了问题），您会在迭代器中得到一个 Python 异常（太多递归）。因此，我们应该合并子叶子而不是构建完整的树（并且我们构建具有 N 个叶子的分支而不是具有 2 个叶子的分支）。
我的代码版本如下：
class Merge:
def __init__(self,value=None,parent=None,subs=None):
self.value = value
self.parent = parent
self.subs = subs
self.root = None
if self.subs:
subs_a,subs_b = self.subs
if subs_a.subs:
subs_a = subs_a.subs
else:
subs_a = [subs_a]
if subs_b.subs:
subs_b = subs_b.subs
else:
subs_b = [subs_b]
self.subs = subs_a+subs_b
for s in self.subs:
s.parent = self
s.root = None
def get_ancestor(self):
cur = self if self.root is None else self.root
while cur.parent is not None:
cur = cur.parent
if cur != self:
self.root = cur
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
def treeconsolidate(array):
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 settomerge in array:
frm = settomerge.pop()
for to in settomerge:
mra = dic[frm].get_ancestor()
mrb = dic[to].get_ancestor()
if mra == mrb:
continue
mr = Merge(subs=[mra,mrb])
merge_heads.remove(mra)
merge_heads.remove(mrb)
merge_heads.add(mr)
resulting_sets = [set(merge) for merge in merge_heads]
return resulting_sets
在小型合并中，这不会改变很多事情，但我的经验表明，在包含许多元素的巨大集合中爬上树会花费很多：在我的例子中，我必须处理 100k 个集合，每个集合包含 2 到 1000 个元素，每个元素可能出现在 1 到 1000 个集合中...