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
zealinux
V2EX  ›  Python

求教 Python 合并元组算法

  •  
  •   zealinux · 2018-12-12 17:41:20 +08:00 · 2866 次点击
    这是一个创建于 1934 天前的主题,其中的信息可能已经有所发展或是发生改变。

    问个技术问题:

    比如: [("a", "b"), ("b", "c"), ("e", "f")]

    合并成

    [set("a", "b", "c"), set("e, "f")]

    (即与有一个元素有交集的,就合并进来)

    ============= 原列表中有一千个元组,半天没出结果

    我写的代码:

    #     l = [("a", "b"), ("b", "c"), ("e", "f")]
    
    def merger(l):
        out_list = []
        for item in l:
            temp_set = set(item)
    
            if len(out_list) == 0:
                out_list.append(temp_set)
            else:
                for item_set in out_list:
                    if len(temp_set & item_set) > 0:
                        item_set.update(temp_set)
                    else:
                        out_list.append(temp_set)
    
    13 条回复    2018-12-13 11:34:05 +08:00
    doraemon1293
        1
    doraemon1293  
       2018-12-12 18:17:10 +08:00
    set(itertools.chain(*arr))
    doraemon1293
        2
    doraemon1293  
       2018-12-12 18:18:25 +08:00
    没仔细看题,,,,忽略我写的吧..
    sikariba
        3
    sikariba  
       2018-12-12 18:23:17 +08:00
    不确定你程序半天没出结果的原因,但是你的 inner loop 里面不应该再从头遍历 out_list 了,因为前面的元素已经遍历过了,你把 l 里的元素换个顺序,改成[ ("e", "f"), ("a", "b"), ("b", "c")]再运行试试,肯定有重复的
    doraemon1293
        4
    doraemon1293  
       2018-12-12 18:24:19 +08:00
    union find
    ```
    from collections import defaultdict


    class DSU:
    def __init__(self):
    self.weights = {}
    self.parents = {}

    def find(self, x):
    if x not in self.parents:
    self.parents[x] = x
    self.weights[x] = 1
    return x
    else:
    path = [x]
    while self.parents[path[-1]] != path[-1]:
    path.append(self.parents[path[-1]])
    root = path[-1]
    for node in path:
    self.parents[node] = root
    return root

    def union(self, elements):
    roots = [self.find(e) for e in elements]
    heaviest_root = max([(self.weights[root], root) for root in roots])[1]
    for root in roots:
    if root != heaviest_root:
    self.weights[heaviest_root] += self.weights[root]
    self.parents[root] = heaviest_root


    def merger(A):
    """
    :type A: List[int]
    :rtype: int
    """
    dsu = DSU()
    for a in A:
    dsu.union(a)
    d=defaultdict(set)
    for k,x in dsu.parents.items():
    d[x].add(k)
    return list(d.values())
    ```
    Jex
        5
    Jex  
       2018-12-12 18:29:29 +08:00   ❤️ 1
    如果是 [("a", "b"), ("b", "c"), ("c", "d")] 呢?全合并成一个?
    mmixxia
        6
    mmixxia  
       2018-12-12 18:30:12 +08:00
    建立一个无向图,然后输出 里面所有没有连接在一起的子图就可以了,非常简单的。
    sikariba
        7
    sikariba  
       2018-12-12 18:38:54 +08:00
    你程序死循环的原因应该是这里
    ```
    for item_set in out_list:
    if len(temp_set & item_set) > 0:
    item_set.update(temp_set)
    else:
    out_list.append(temp_set)
    ```
    你不断迭代 out_list,然后又不断对它 append,就永远都遍历不完。常见错误了。
    rabbbit
        8
    rabbbit  
       2018-12-12 19:04:02 +08:00
    ihciah
        9
    ihciah  
       2018-12-12 19:11:02 +08:00   ❤️ 1
    这不是并查集嘛
    aijam
        10
    aijam  
       2018-12-12 19:27:00 +08:00
    mskf
        11
    mskf  
       2018-12-12 20:44:41 +08:00
    并查集。。。
    hustlibraco
        12
    hustlibraco  
       2018-12-12 22:42:46 +08:00
    # coding=utf-8
    # input = [('a', 'b'), ('b', 'c'), ('e', 'f')]
    # output = [{'a', 'b', 'c'}, {'e', 'f'}]


    def union_set(items):
    ret = []
    mark = {}
    for item in items:
    for n in item:
    if n in mark:
    for m in item:
    ret[mark[n]].add(m)
    mark[m] = mark[n]
    break
    else:
    index = len(ret)
    s = set()
    for n in item:
    s.add(n)
    mark[n] = index
    ret.append(s)

    return ret


    if __name__ == "__main__":
    inputs = [('a', 'b'), ('b', 'c'), ('a', 'e', 'f')]
    print(union_set(inputs))
    zealinux
        13
    zealinux  
    OP
       2018-12-13 11:34:05 +08:00
    @aijam great,代码比较优雅

    新学到两个技能:

    `for-else`
    `集合可用作判断,空集合可当 False`
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2900 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 14:17 · PVG 22:17 · LAX 07:17 · JFK 10:17
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.