"Raymond Hettinger" <pyt...@rcn.com> wrote in message
news:fb1feeeb-c430-4ca7-9e76-fea02ea3e...@v23g2000pro.googlegroups.com...
> [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 = [0]*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[0][indices[0]])
indices[0] += 1
except IndexError:
pass
--
http://mail.python.org/mailman/listinfo/python-list
