Merging ordered lists

Peter Otten __peter__ at web.de
Sun Jun 1 10:49:34 CEST 2008


Peter Otten wrote:

> #untested

Already found two major blunders :(

# still untested
import difflib

def _merge(a, b):
    sm = difflib.SequenceMatcher(None, a, b)
    for op, a1, a2, b1, b2 in sm.get_opcodes():
        if op == "insert":
            yield b[b1:b2]
        elif op == "replace":
            yield a[a1:a2]
            yield b[b1:b2]
        else: # delete, equal
            yield a[a1:a2]

def merge(a, b):
    return sum(_merge(a, b), [])

def merge_to_unique(sources):
    return unique(reduce(merge, sorted(sources, key=len, reverse=True)))

def unique(items):
    u = set(items)
    if len(u) == len(items):
        return items
    result = []
    for item in items:
        if item in u:
            result.append(item)
            u.remove(item)
    return result





More information about the Python-list mailing list