itertools.intersect?

[Arnaud Delobelle]

David Wilson <dw at botanicus.net> writes:

> Hi,
>
> During a fun coding session yesterday, I came across a problem that I
> thought was already solved by itertools, but on investigation it seems
> it isn't.
>
> The problem is simple: given one or more ordered sequences, return
> only the objects that appear in each sequence, without reading the
> whole set into memory. This is basically an SQL many-many join.

As it is a nice little problem I tried to find a solution today.  FWIW,
here it is (tested extensively only on the example below :):

def intersect(iterables):
    nexts = [iter(iterable).next for iterable in iterables]
    v = [next() for next in nexts]
    while True:
        for i in xrange(1, len(v)):
            while v[0] > v[i]:
                v[i] = nexts[i]()
            if v[0] < v[i]: break
        else:
            yield v[0]
        v[0] = nexts[0]()

>>> list(intersect([[1, 100, 142, 322, 12312],
...                 [2, 100, 101, 322, 1221],
...                 [100, 142, 322, 956, 1222]]))
[100, 322]