CODEWITHSUNDEEP
python
Paschalis
Paschalis

Reputation: 181

In-place modification of a python list when condition is met

I've got a list of numbers, and I also compute all possible combinations of two of this list. What I want to do is check whether the sum of the first combination is less than 5, and if so, choose a random number out of the 2 from the combination, remove that number from the initial list and re-calculate the combinations, etc.

import itertools
import random

numbers = [1,2,3,4,5,6,7,8,9,10]

all_combos = list(itertools.combinations(numbers, 2))

for combo in all_combos:
    if combo[0] + combo[1] < 5:
        choice = random.choice([combo[0],combo[1]])
        numbers.remove(choice)

The error I get

ValueError: list.remove(x): x not in list

Initially I thought it was the inplace changing of the list in combination with the for loop that caused this, so I also tried implementing a while loop, but it always ends up being an infinite loop since I can't seem to find the correct condition for it.

Upvotes: 1

Views: 153

Answers (4)

Mad Physicist
Mad Physicist

Reputation: 114230

Right now, you are removing a number from numbers but not updating all_combos. That means the number will almost certainly show up in all_combos again, but be missing from numbers. You do not need to regenerate all possible combinations every time you remove a number, but you do need to filter all_combos and adjust your position accordingly. A simple method for doing so is to maintain a list of booleans that you update every time you discard a number:

from itertools import combinations
from random import choice

numbers = list(range(1, 11))

all_combos = list(combinations(numbers, 2))

valid = [True] * len(all_combos)
for i, combo in enumerate(all_combos):
    if not valid[i]: continue
    if sum(combo) < 5:
        c = random.choice(combo)
        valid[i + 1:] = (valid[j] and c not in all_combos[j] for j in range(i + 1, len(all_combos)))

This algorithm is much cheaper than regenerating the entire list of combinations at every step since it just skips invalidated combos. You could further reduce the complexity from O(n2) (because you revisit the entire tail of all_combos at each step) by using a set to keep track of discarded elements and deciding which ones to skip on the fly. This will be O(n2) because set lookup is ostensibly O(1):

from itertools import combinations
from random import choice

numbers = list(range(1, 11))

all_combos = list(combinations(numbers, 2))

dropped = set()
for i, combo in enumerate(all_combos):
    if any(x in dropped for x in dropped): continue
    if sum(combo) < 5:
        dropped.add(random.choice(combo))

Upvotes: 0

tdelaney
tdelaney

Reputation: 77337

As mentioned, you may choose the same number more than once, causing the error. You could put the numbers you want to remove in a set, which removes duplicates, and do the remove later.

import itertools
import random

numbers = [1,2,3,4,5,6,7,8,9,10]

all_combos = list(itertools.combinations(numbers, 2))

remove_this = {}
for combo in all_combos:
    if combo[0] + combo[1] < 5:
        choice = random.choice([combo[0],combo[1]])
        remove_this.add(choice)
for choice in remove_this:
    numbers.remove(choice)

That can be reduced to

remove_this = {random.choice(combo)
        for combo in itertools.combinations(numbers, 2)
        if sum(combo) < 5}
for choice in remove_this:
    numbers.remove(choice)
print(numbers)

Upvotes: 1

Mark
Mark

Reputation: 92440

If you would like to actually recalculate the combinations as you say in the question, you need to put that itertools.combinations call somewhere in the loop and regenerate it after mutating numbers.

One way would be to use a while loop and only break once you've made it through the combinations without finding more pairs that meet your criteria:

import itertools
import random

numbers = [1,2,3,4,5,6,7,8,9,10]


while True:    
    all_combos = itertools.combinations(numbers, 2)
    try:
        pair = next(p for p in all_combos if sum(p) < 5)
    except StopIteration:
        break
    choice = random.choice(pair)
    numbers.remove(choice)

This will make a small difference in the statistics of the choices because removing 2 in the first iteration removes all possibility of removing 3 in the pair (2, 3) later where simply removing it from numbers and continuing leaves that choice in the combinations. This means your odds of having 3 left in your number list are higher than the other way of doing this.

Upvotes: 2

dawg
dawg

Reputation: 103744

Since it is random, you may end up trying to remove a number already removed.

Just wrap in a try / except:

    try:
        numbers.remove(choice)
    except ValueError:
        pass

Or, ask permission:

    if choice in numbers: 
        numbers.remove(choice)

Upvotes: 1

Related Questions