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

Accepted Answer

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.

iterating over a growing set in python

Solution

Problem