# itertools.intersect?

Andrew Henshaw andrew.henshaw at gtri.gatech.edu
Mon Jun 15 10:40:24 EDT 2009

```"Raymond Hettinger" <python at rcn.com> wrote in message
> [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

Here's my translation of your code to support variable number of streams:

def intersect(*s):
num_streams = len(s)
indices = *num_streams
try:
while True:
for i in range(num_streams):
j = (i + 1) % num_streams
if s[i][indices[i]] < s[j][indices[j]]:
indices[i] += 1
break
else:
print(s[indices])
indices += 1
except IndexError:
pass

```