iterating over a growing set in python

Question

I have a set, setOfManyElements, which contains n elements. I need to go through all those elements and run a function on each element of S:

for s in setOfManyElements:
   elementsFound=EvilFunction(s)
   setOfManyElements|=elementsFound

EvilFunction(s) returns the set of elements it has found. Some of them will already be in S, some will be new, and some will be in S and will have already been tested.

The problem is that each time I run EvilFunction, S will expand (until a maximum set, at which point it will stop growing). So I am essentially iterating over a growing set. Also EvilFunction takes a long time to compute, so you do not want to run it twice on the same data.

Is there an efficient way to approach this problem in Python 2.7?

LATE EDIT: changed the name of the variables to make them more understandable. Thanks for the suggestion

Answer 1

I suggest an incremental version of 6502's approach:

seen   = set(initial_items)
active = set(initial_items)

while active:
    next_active = set()
    for item in active:
        for result in evil_func(item):
            if result not in seen:
                seen.add(result)
                next_active.add(result)
    active = next_active

This visits each item only once, and when finished seen contains all visited items.

For further research: this is a breadth-first graph search.

Answer 2

You can just keep a set of already visited elements and pick a non-yet-visited element each time

visited = set()
todo = S
while todo:
    s = todo.pop()
    visited.add(s)
    todo |= EvilFunction(s) - visited