Python 怎么实现归并集合功能？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐学习书目

› Learn Python the Hard Way

Python Sites

› PyPI - Python Package Index

› http://diveintopython.org/toc/index.html

› Pocoo

值得关注的项目

› PyPy

› Celery

› Jinja2

› Read the Docs

› gevent

› pyenv

› virtualenv

› Stackless Python

› Beautiful Soup

› 结巴中文分词

› Green Unicorn

› Sentry

› Shovel

› Pyflakes

› pytest

Python 编程

› pep8 Checker

Styles

› PEP 8

› Google Python Style Guide

› Code Style from The Hitchhiker's Guide

这是一个创建于 2086 天前的主题，其中的信息可能已经有所发展或是发生改变。

比如

输入：[(A, B), (B, C), (X,Y)]
输出：[(A, B, C), (X, Y)]

即归并有相同元素的集合。

有没有现成的库？

或者自己实现的化思路是什么样的？

第 1 条附言 · 2019-03-13 17:03:04 +08:00

为求表示简单，省略 set()，
A，A 指代同一字符串，比如” UUID_A"

归并

集合

Python

现成

13 条回复 • 2019-03-13 20:38:59 +08:00

niknik

2019-03-13 16:41:04 +08:00

楼下帮我回一下，我上个厕所👇

shyrock

2019-03-13 16:42:55 +08:00

这不是元组列表吗。。。哪里有集合。。。

bumz

2019-03-13 17:01:10 +08:00

并查集？

bumz

2019-03-13 17:01:26 +08:00

@shyrock #2 逻辑上的集合

ybbswc

2019-03-13 17:03:20 +08:00 via Android

首先判断是否有相同元素，有的话就作并集。楼下来吧。(ーー;)

bumz

2019-03-13 17:33:08 +08:00

亲测并查集可行，复杂度 O(n)，n 为输入中唯一元素的个数 * 每种元素平均出现次数

https://gist.github.com/bumfo/26fc4865e27b48385ed650cd08fe6004

bumz

2019-03-13 17:34:34 +08:00

@bumz #6 想要 set 的话把 tuple 改成 set 一样

bumz

2019-03-13 17:41:09 +08:00

@bumz #6 复杂度 O(n log m)，m 是不同元素的个数，n 是 m * 每个元素的平均出现次数

bumz

2019-03-13 17:45:06 +08:00

@ybbswc #5 这种做法复杂度 O(ab), a 是集合的个数，b 是每个集合中元素的个数的平均值

lasuar

2019-03-13 17:50:19 +08:00

```
a = [(1,2), (2,3)]
b = [(1,2)]

print(set(a) | set(b))
```

strict

2019-03-13 18:36:38 +08:00

复杂度目前想到的全是 m*n

xor

2019-03-13 20:28:01 +08:00 via iPhone

@strict 并查集可以 n log m

xor

2019-03-13 20:38:59 +08:00 via iPhone

@xor 并查集可以做到在现实中 O(m)
严格来讲 O(m α(n)) 但是现实中 α(n) <= 4