Strange behavior of list iteration using for loop in python

Question

I've come across a situation where my python code behaves differently in similar cases. Here's the code:

import time
def greedy_cow_transport(cows,limit=10):
    weights = []
    for weight in cows.values():
        weights.append(weight)
    weights.sort(reverse=True)
    cows_copy = cows.copy()
    all_trips = []
    while (len(weights) > 0):
        avail_weight = limit
        curr_trip = []
        for weight in weights:
            if weight <= avail_weight:
                for n, w in cows_copy.items():
                    if weight == w:
                        curr_trip.append(n)
                        weights.remove(weight)
                        cows_copy.pop(n, None)
                        avail_weight -= w
                        break
        all_trips.append(curr_trip)
    return all_trips
cows = {'Lola': 2, 'Oreo': 2, 'Millie': 2, 'Betsy': 2, 'Moo Moo': 2, 'Milkshake': 2, 'Herman': 2, 'Florence': 2, 'Maggie': 2, 'Henrietta': 2}
limit=100
print(cows)
print(greedy_cow_transport(cows))

Instead of greedy_cow_transport returning the 2 list of lists of 5 members, it return 3 different lists of 5 3 2 members. Please explain why its happening? I know, I might be missing some subtle detail but I need help. Can't figure out the error. Thanks.

Your code is supposed to break a dict in parts, each part having a total value <= limit, right ? — Ealhad, Mar 30 '17 at 13:00
Extremely minor side-note: Your whole initialization of `weights` could simplify to `weights = sorted(cows.values(), reverse=True)`. Even if sorting wasn't needed, explicit loops with repeated `append`s of the unmodified values would simplify to a single `.extend` call (or if the list is initially empty, just constructing it with `list(someiterable)` directly). — ShadowRanger, Mar 30 '17 at 13:31

jeremye · Accepted Answer · 2017-03-30T14:07:47.457

The problem is with the loop for weight in weights:

The loop is iterating over the items in the list, but the Python loop uses the position of the item in order to do that. When you remove an item with weights.remove(weight) the list shrinks while the position increases by 1 as it normally would. Basically, because you are removing items from weights while iterating over the list, it goes over every other item—hence the different list lengths as it shrinks (you can verify this by setting all the weights equal to 1; you'll get the same results as with 2)

An example of what's going on:

list = [1, 2, 3, 4, 5]
for item in list:
    print(item)
    list.remove(item)
    print(list)

# --> 1
# --> [2, 3, 4, 5]
# --> 3
# --> [2, 4, 5]
# --> 5
# --> [2, 4]

^^ Notice how it only iterates every other item. Precisely what is happening with your weights.

An easy fix is to have your for loop iterate over a copy, while you remove from the original:

list = [1, 2, 3, 4, 5]
for item in list.copy():
    print(item)
    list.remove(item)
    print(list)

# --> 1
# --> [2, 3, 4, 5]
# --> 2
# --> [3, 4, 5]
# --> 3
# --> [4, 5]
# --> 4
# --> [5]
# --> 5
# --> []

WOW! Look at that work so beautifully. For your cows that would look like this:

def greedy_cow_transport(cows,limit=10):
    weights = []
    for weight in cows.values():
        weights.append(weight)
    weights.sort(reverse=True)
    cows_copy = cows.copy()
    all_trips = []
    while (len(weights) > 0):
        avail_weight = limit
        curr_trip = []
        for weight in weights.copy():
            if weight <= avail_weight:
                for n, w in cows_copy.items(): # <--!!! THE CHANGE IS HERE
                    if weight == w:
                        curr_trip.append(n)
                        weights.remove(weight)
                        cows_copy.pop(n, None)
                        avail_weight -= w
                        break
        all_trips.append(curr_trip)
    return all_trips
cows = {'Lola': 2, 'Oreo': 2, 'Millie': 2, 'Betsy': 2, 'Moo Moo': 2, 'Milkshake': 2, 'Herman': 2, 'Florence': 2, 'Maggie': 2, 'Henrietta': 2}
print(greedy_cow_transport(cows))

# --> [['Oreo', 'Milkshake', 'Herman', 'Florence', 'Lola'], ['Maggie', 'Millie', 'Henrietta', 'Betsy', 'Moo Moo']]

And voila! Hope you enjoyed.

@ShadowRanger added that in older versions of Python, list did not have a copy method, and so an alternative to list.copy() is using an empty slice like so list[:].

Minor note: If you're on older Python (pre-3.3), `list` lacks a `copy` method (it was added later for consistency with stuff like `set` and `dict`). If your code might run on earlier versions of Python, `for weight in weights[:]:` will work just fine on any version; the "empty" slice is the Python idiom for shallow copying any arbitrary sequence. — ShadowRanger, Mar 30 '17 at 13:29
Instead of creating a copy of the list, you can also loop over position indices in reverse order, .i.e., from back. — jure, Mar 30 '17 at 13:30
Brilliant addition ShadowRanger. I don't know the proper protocol, should I add your addition to my answer or leave it to be found in your comment? — jeremye, Mar 30 '17 at 13:31
You can edit and leave a note at the bottom of your answer, stating the idea came from @ShadowRanger. Most people don't really read the comments. — Ealhad, Mar 30 '17 at 14:02

Strange behavior of list iteration using for loop in python

1 Answers1