集合并集查找算法

2022-01-17 00:00:00 python algorithm set

问题描述

我有数千行 1 到 100 个数字，每行定义一组数字以及它们之间的关系.我需要获取相关数字的集合.

I have thousands of lines of 1 to 100 numbers, every line define a group of numbers and a relationship among them. I need to get the sets of related numbers.

小例子:如果我有这 7 行数据

Little Example: If I have this 7 lines of data

T1 T2
T3 
T4
T5
T6 T1
T5 T4
T3 T4 T7

我需要一个不那么慢的算法来知道这里的集合是:

I need a not so slow algorithm to know that the sets here are:

T1 T2 T6 (because T1 is related with T2 in the first line and T1 related with T6 in the line 5)
T3 T4 T5 T7 (because T5 is with T4 in line 6 and T3 is with T4 and T7 in line 7)

但是当你有非常大的集合时，在每个大集合中搜索一个 T(x) 并进行集合并集......等等.

but when you have very big sets is painfully slow to do a search of a T(x) in every big set, and do unions of sets... etc.

您是否有提示以不那么蛮力的方式执行此操作?

Do you have a hint to do this in a not so brute force manner?

我正在尝试在 Python 中执行此操作.

I'm trying to do this in Python.

解决方案

一旦你构建了数据结构，你到底想对它运行什么查询?向我们展示您现有的代码.什么是 T(x)?您谈论数字组"，但您的样本数据显示 T1、T2 等；请解释一下.

Once you have built the data structure, exactly what queries do you want to run against it? Show us your existing code. What is a T(x)? You talk about "groups of numbers" but your sample data shows T1, T2, etc; please explain.

你读过这个吗:http://en.wikipedia.org/wiki/Disjoint-set_data_structure

尝试查看以下 Python 实现:http://code.activestate.com/recipes/215912-union-find-data-structure/

Try looking at this Python implementation: http://code.activestate.com/recipes/215912-union-find-data-structure/

或者你可以自己写一些相当简单易懂的东西，例如

OR you can lash up something rather simple and understandable yourself, e.g.

[更新:全新代码]

class DisjointSet(object):

    def __init__(self):
        self.leader = {} # maps a member to the group's leader
        self.group = {} # maps a group leader to the group (which is a set)

    def add(self, a, b):
        leadera = self.leader.get(a)
        leaderb = self.leader.get(b)
        if leadera is not None:
            if leaderb is not None:
                if leadera == leaderb: return # nothing to do
                groupa = self.group[leadera]
                groupb = self.group[leaderb]
                if len(groupa) < len(groupb):
                    a, leadera, groupa, b, leaderb, groupb = b, leaderb, groupb, a, leadera, groupa
                groupa |= groupb
                del self.group[leaderb]
                for k in groupb:
                    self.leader[k] = leadera
            else:
                self.group[leadera].add(b)
                self.leader[b] = leadera
        else:
            if leaderb is not None:
                self.group[leaderb].add(a)
                self.leader[a] = leaderb
            else:
                self.leader[a] = self.leader[b] = a
                self.group[a] = set([a, b])

data = """T1 T2
T3 T4
T5 T1
T3 T6
T7 T8
T3 T7
T9 TA
T1 T9"""
# data is chosen to demonstrate each of 5 paths in the code
from pprint import pprint as pp
ds = DisjointSet()
for line in data.splitlines():
    x, y = line.split()
    ds.add(x, y)
    print
    print x, y
    pp(ds.leader)
    pp(ds.group)

这是最后一步的输出:

T1 T9
{'T1': 'T1',
 'T2': 'T1',
 'T3': 'T3',
 'T4': 'T3',
 'T5': 'T1',
 'T6': 'T3',
 'T7': 'T3',
 'T8': 'T3',
 'T9': 'T1',
 'TA': 'T1'}
{'T1': set(['T1', 'T2', 'T5', 'T9', 'TA']),
 'T3': set(['T3', 'T4', 'T6', 'T7', 'T8'])}

相关文章