itertools.intersect?

[Raymond Hettinger]

[David Wilson]
> 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.

FWIW, this is equivalent to the Welfare Crook problem in David Gries
book, The Science of Programming, http://tinyurl.com/mzoqk4 .


> I thought it could be accomplished through recursively embedded
> generators, but that approach failed in the end.

Translated into Python, David Gries' solution looks like this:

def intersect(f, g, h):
    i = j = k = 0
    try:
        while True:
            if f[i] < g[j]:
                i += 1
            elif g[j] < h[k]:
                j += 1
            elif h[k] < f[i]:
                k += 1
            else:
                print(f[i])
                i += 1
    except IndexError:
        pass

streams = [sorted(sample(range(50), 30)) for i in range(3)]
for s in streams:
    print(s)
intersect(*streams)


Raymond