Francis Carr coldtortuga at
Mon Jun 22 16:08:16 EDT 2009

On Jun 11, 6:23 pm, Mensanator <mensana... at> wrote:
> Removing the duplicates could be a big problem.

It is fairly easy to ignore duplicates in a sorted list:
from itertools import groupby
def unique(ordered):
    """Yield the unique elements from a sorted iterable.
    for key,_ in groupby(ordered):
        yield key

Combining this with some ideas of others, we have a simple, complete
def intersect(*ascendingSeqs):
    """Yield the intersection of zero or more ascending iterables.
    if N==0:

    unq = [unique(s) for s in ascendingSeqs]
    val = [ for u in unq]
    while True:
        for i in range(N):
            while val[i-1] > val[i]:
                val[i] = unq[i].next()
        if val[0]==val[-1]:
            yield val[0]
            val[-1] = unq[-1].next()

This works with empty arg-lists; combinations of empty, infinite and
finite iterators; iterators with duplicate elements; etc.  The only
requirement is that all iterators are sorted ascending.

 -- FC

More information about the Python-list mailing list