Modifying a set while iterating over it

Question

I would like to iterate over a set while I'm deleting items from it. There are similar questions for deleting one item at the time or for lists, but they do not work for my case.

The code follows; I iterate over a set ZN and in the end of the iteration I'm removing a few items (the ones belonging to the set temp). But the iteration is still happening over the "original" ZN.

How can I modify this code to change the set ZN while I'm iterating over it?

def CyclotomicCosets(q,n):
    N=q^n-1
    ZN=set(range(N))
    Cosets=[]
    for i in ZN:
        tmp=set([])
        for j in range(n):
            tmp.add( i*(q^j) %N)
        Cosets.append(list(tmp))
        ZN=ZN.difference(tmp) # <------------ Does not do what I want
    return(Cosets)

Possible duplicate of [delete items from a set while iterating over it](http://stackoverflow.com/questions/16551334/delete-items-from-a-set-while-iterating-over-it) — 200_success, Feb 02 '16 at 07:29

Martijn Pieters · Accepted Answer · 2013-05-18T16:21:45.903

Use a while loop and .pop() values to process from the set:

def CyclotomicCosets(q, n):
    N = q ^ n - 1
    ZN = set(range(N))
    Cosets = []
    while ZN:
        i = ZN.pop()
        tmp = {i * (q ^ j) % N for j in range(n)}
        Cosets.append(list(tmp))
        ZN -= tmp
    return Cosets

Note that I replaced your inner for loop with a set comprehension to make it a little faster and more compact. These were introduced in Python 2.7 and Python 3, in earlier versions of python you can use a generator expression instead:

tmp = set(i * (q ^ j) % N for j in range(n))

Your original mistake was to replace ZN rather than update it:

ZN=ZN.difference(tmp)

This did not alter the original set you were using in the for loop. Rather, you are creating a new set and point the ZN reference to that.

However, you cannot modify a set while iterating over it, so even an in-place difference would not have worked; you would have to use ZN -= tmp or ZN.difference_update(tmp) but that would lead to exceptions instead:

>>> ZN = set(range(3))
>>> for i in ZN:
...     ZN -= set([2])
... 
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: Set changed size during iteration

The corrected code gives:

>>> CyclotomicCosets(3, 5)
[[0], [0, 1, 2, 3], [0, 1, 4, 5], [0, 4, 5, 6]]

Alternatively, loop over range(N) instead, and keep a set of values you've already processed:

def CyclotomicCosets(q, n):
    N = q ^ n - 1
    Cosets = []
    seen = set()
    for i in range(N):
        if i in seen: continue
        tmp = {i * (q ^ j) % N for j in range(n)}
        Cosets.append(list(tmp))
        seen |= tmp
    return Cosets

Thank you! Copy-pasting your suggested code gave me: `Syntax Error: Cosets.append(list(tmp))` — geo909, May 18 '13 at 16:19
@geo909: What version of Python? I used a set comprehension, which is only available in Python 2.7 and Python 3.x. — Martijn Pieters, May 18 '13 at 16:20
To be honest I am using sage ("notebook" browser interface, accessing my university's sage via my browser), where you essentially are coding in python with extra math libraries (I guess, I'm quite new to coding and this). I can see that the sage version is 4.3 (dec 2009) but for the life of it I cannot find a way to get the python version through the notebook interface. On another note, I changed the code a bit so that it works for me, I'll update my question.. — geo909, May 18 '13 at 16:33
Btw voting up requires more reputation than I have, sorry :) — geo909, May 18 '13 at 16:34
Sage 4.3 is quite old, and uses Python 2.6.4, I believe. I recommend that @geo909 update to the latest Sage, which uses 2.7, and has a TON of newer functionality... though if s/he has some custom code maybe that will be problematic. — kcrisman, May 20 '13 at 12:03

Modifying a set while iterating over it

1 Answers1