通过应用传递闭包创建唯一编号列表 [英] Create a list of unique numbers by applying transitive closure

问题描述

我有一个元组列表(每个元组由2个数字组成)，例如:

I have a list of tuples (each tuple consists of 2 numbers) like:

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

可以说，这些数字是某些db对象(记录)的ID，而在元组中，则存在重复对象的ID.这意味着1和2是重复的. 1和3是重复的，这意味着2和3也都是重复的.

Lets say, these numbers are ids of some db objects (records) and inside a tuple, there are ids of duplicate objects. Which means 1 and 2 are duplicate. 1 and 3 are duplicate which means 2 and 3 are also duplicate.

如果a == b和b == c，则a == c

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

现在，我想将所有这些重复的对象ID合并到一个元组中，如下所示:

Now I want to merge all these duplicate objects ids into a single tuple like this:

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

我知道我可以使用循环和冗余匹配来做到这一点.我只想要一些处理/计算量少(如果有的话)的更好的解决方案.

I know I can do this using loops and redundant matches. I just want some better solution with low processing / calculations (if there is any).

推荐答案

我认为最有效的方法是使用

I think the most efficient way to achieve this will be using set as:

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上):

---

Comparison with other answers (on Python 3.4):

• 此答案:6.238126921001822

• This answer: 6.238126921001822

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

威廉的解决方案:29.115453064994654 (与类声明相关的时间不包括在内)

Willem's solution: 29.115453064994654 (Time related to declaration of class is excluded)

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

hsfzxjy的解决方案:10.049749890022213

hsfzxjy's solution: 10.049749890022213

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

这篇关于通过应用传递闭包创建唯一编号列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！