CODEWITHSUNDEEP
pythonsetiterationsage
geo909
geo909

Reputation: 434

Modifying a set while iterating over it

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)

Upvotes: 2

Views: 11330

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1123400

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

Upvotes: 1

Related Questions