Removing List from List of Lists with condition

Question

I have this list of projects, and I want to remove it one by one start from last item to item-n until it reach some total value of budget = 325.000

from collections import namedtuple

Item = namedtuple('Item', 'region sector name budget target performance'.split())

sorted_KP = [Item(region='H', sector='2', name='H3', budget=7000.0, target=1.0, performance=4.0),
Item(region='H', sector='2', name='H10', budget=35000.0, target=15.0, performance=1.0),
Item(region='I', sector='2', name='I6', budget=50000.0, target=5.0, performance=0.40598931548848194),
Item(region='E', sector='4', name='E5', budget=75000.0, target=30.0, performance=0.0663966081766),
Item(region='C', sector='1', name='C1', budget=75000.0, target=50.0, performance=0.0308067750379),
Item(region='C', sector='1', name='C2', budget=75000.0, target=50.0, performance=0.0308067750379),
Item(region='C', sector='5', name='C4', budget=75000.0, target=50.0, performance=0.0308067750379),
Item(region='I', sector='2', name='I5', budget=100000.0, target=5.0, performance=0.40598931548848194),
Item(region='E', sector='4', name='E1', budget=100000.0, target=30.0, performance=0.0663966081766),
Item(region='D', sector='5', name='D21', budget=60000.0, target=4.0, performance=0.2479775110248),
Item(region='D', sector='5', name='D30', budget=10000.0, target=1.0, performance=0.1653183406832),
Item(region='D', sector='1', name='D23', budget=30000.0, target=20.0, performance=0.023659703723372342),
Item(region='C', sector='5', name='C3', budget=150000.0, target=75.0, performance=0.0308067750379),
Item(region='D', sector='5', name='D20', budget=30000.0, target=5.0, performance=0.0826591703416),
Item(region='H', sector='2', name='H6', budget=310576.0, target=1.0, performance=4.0),
Item(region='H', sector='3', name='H5', budget=9500.0, target=1.0, performance=0.1172008400616),
Item(region='E', sector='6', name='E3', budget=100000.0, target=30.0, performance=0.03747318294316411),
Item(region='G', sector='3', name='G17', budget=75000.0, target=20.0, performance=0.04132095963602382),
Item(region='C', sector='4', name='C5', budget=75000.0, target=25.0, performance=0.0308067750379),
Item(region='C', sector='2', name='C6', budget=30000.0, target=5.0, performance=0.0616135500758),
Item(region='C', sector='2', name='C7', budget=30000.0, target=5.0, performance=0.0616135500758),
Item(region='D', sector='6', name='D22', budget=65190.0, target=30.0, performance=0.020332158889648923),
Item(region='D', sector='5', name='D3', budget=100000.0, target=20.0, performance=0.0413295851708),
Item(region='D', sector='5', name='D4', budget=100000.0, target=20.0, performance=0.0413295851708),
Item(region='A', sector='1', name='A12', budget=25000.0, target=25.0, performance=0.00749432996938),
Item(region='A', sector='1', name='A13', budget=25000.0, target=25.0, performance=0.00749432996938),
Item(region='A', sector='3', name='A25', budget=4500.0, target=1.0, performance=0.02997731987752),
Item(region='A', sector='5', name='A26', budget=4500.0, target=1.0, performance=0.02997731987752),
Item(region='A', sector='1', name='A27', budget=4500.0, target=1.0, performance=0.02997731987752),
Item(region='A', sector='1', name='A29', budget=4500.0, target=1.0, performance=0.02997731987752),
Item(region='A', sector='3', name='A30', budget=4500.0, target=1.0, performance=0.02997731987752)]

But beside the total value, I have two others conditions of the item whether it should be removed or not.

First, after the item is removed there still remain at least one item in the list of lists that represent the same region

Second, after the item is removed there still remain at least one item that represent the same sector

For example, I can remove the last item because it represent region "A" and there left 5 items that also represent region "A". Also it represent sector "3" and there left 3 items that represent sector "3".

This removal and checking repeated until I reach total budget of removal at least 325.000

I did this code, but I can not get what I need. Please help me to correct it.

from collections import Counter
unpack = []
for item in sorted_KP:
    item_budget = item[3]
    sum_unpack = sum(item[3] for item in unpack)
    budget = 325000

    remaining = []
    for item in sorted_KP:
         if item not in unpack:
             remaining.append(item)

    region_el = [item[0] for item in remaining]
    counter_R_el = Counter(region_el)

    sector_el = [item[1] for item in remaining]
    counter_S_el = Counter(sector_el)

    if counter_R_el >= 1 or counter_S_el >= 1:
        if sum_unpack <= budget:
            unpack.append(item)

for item in unpack:
    print "\t", item

Here is what I got with my code, item-25 is still removed when it should not:

unpack =Item(region='A', sector='3', name='A30', budget=4500.0, target=1.0, performance=0.02997731987752)
    Item(region='A', sector='1', name='A29', budget=4500.0, target=1.0, performance=0.02997731987752)
    Item(region='A', sector='1', name='A27', budget=4500.0, target=1.0, performance=0.02997731987752)
    Item(region='A', sector='5', name='A26', budget=4500.0, target=1.0, performance=0.02997731987752)
    Item(region='A', sector='3', name='A25', budget=4500.0, target=1.0, performance=0.02997731987752)
    Item(region='A', sector='1', name='A13', budget=25000.0, target=25.0, performance=0.00749432996938)
    Item(region='A', sector='1', name='A12', budget=25000.0, target=25.0, performance=0.00749432996938)
    Item(region='D', sector='5', name='D4', budget=100000.0, target=20.0, performance=0.0413295851708)
    Item(region='D', sector='5', name='D3', budget=100000.0, target=20.0, performance=0.0413295851708)
    Item(region='D', sector='6', name='D22', budget=65190.0, target=30.0, performance=0.020332158889648923)

Item-25 (project name: "A12") can not be removed even though we still have budget to be removed, because if it was remove, there'll be no more item represent region "A", and so on.

While the solution should be:

unpack = [Item(region='A', sector='3', name='A30', budget=4500.0, target=1.0, performance=0.02997731987752),
Item(region='A', sector='1', name='A29', budget=4500.0, target=1.0, performance=0.02997731987752),
Item(region='A', sector='1', name='A27', budget=4500.0, target=1.0, performance=0.02997731987752),
Item(region='A', sector='5', name='A26', budget=4500.0, target=1.0, performance=0.02997731987752),
Item(region='A', sector='3', name='A25', budget=4500.0, target=1.0, performance=0.02997731987752),
Item(region='A', sector='1', name='A13', budget=25000.0, target=25.0, performance=0.00749432996938),
Item(region='D', sector='5', name='D4', budget=100000.0, target=20.0, performance=0.0413295851708),
Item(region='D', sector='5', name='D3', budget=100000.0, target=20.0, performance=0.0413295851708),
Item(region='D', sector='6', name='D22', budget=65190.0, target=30.0, performance=0.020332158889648923),
Item(region='C', sector='2', name='C7', budget=30000.0, target=5.0, performance=0.0616135500758)]

Thank you in advance for your help

Answer 1

Assume that you are using Python 2 as you use print without ().

See the comments in the modified code:

unpack = []
for item in sorted_KP[::-1]: # loop the items in reverse order
    #item_budget = item[3] # variable not used
    sum_unpack = sum(item[3] for item in unpack)
    budget = 325000

    remaining = []
    for x in sorted_KP: # don't use 'item' here as in Python 2, it will modify the variable 'item' in the outer loop
        if x not in unpack:
            remaining.append(x)

    region_el = [x[0] for x in remaining] # don't use 'item' here as well
    counter_R_el = Counter(region_el)

    sector_el = [x[1] for x in remaining] # don't use 'item' here as well
    counter_S_el = Counter(sector_el)

    #if counter_R_el >= 1 or counter_S_el >= 1: # note that result is always True in Python 2
    if counter_R_el[item.region] > 1 and counter_S_el[item.sector] > 1: # check '> 1' instead of '>= 1', and use 'and' instead of 'or'
        if sum_unpack <= budget:
            unpack.append(item)

for item in unpack:
    print "\t", item

My proposed solution:

budget = 325000
sum = 0 # accumulated budget of removed items
removed_KP = [] # holds the removed items
for item in sorted_KP[::-1]:
    # stop checking if over-budget
    if sum >= budget: break
    # check whether there are items with same region and sector
    rcnt = scnt = 0
    for tmp in sorted_KP:
        if tmp.region == item.region: rcnt += 1
        if tmp.sector == item.sector: scnt += 1
    if scnt > 1 and rcnt > 1:
        # this item can be removed based on the constraints
        sorted_KP.remove(item)
        removed_KP.append(item)
        sum += item.budget

# print the removed items
for item in removed_KP:
    print(item)

Answer 2

Updating the answer as when I actually tried to run it I found a few other problems:

• the inner for item in sorted_KP uses the same item counter as the outer loop and overwrites it - always attempting to remove the A30 (last) item
• when switching to item2 in the inner loop I had to also reverse the outer loop order (i.e. start removal from the last line).
• the region/sector counter comparison is incorrect, causing TypeError: unorderable types: Counter() >= int() - need to pick the specific count inside matching the item's region or sector as needed
• incorporated my earlier answer: you need to and your 2 extra conditions, not or them
• incorporated @wwii's comment - indeed the counter comparisons need to be > 1, not >= 1

The actual tested code:

>>> for item in sorted_KP[::-1]:
...     item_budget = item[3]
...     sum_unpack = sum(item[3] for item in unpack)
...     budget = 325000
...     remaining = []
...     for item2 in sorted_KP:
...          if item2 not in unpack:
...              remaining.append(item2)
...     region_el = [item[0] for item in remaining]
...     counter_R_el = Counter(region_el)
...     sector_el = [item[1] for item in remaining]
...     counter_S_el = Counter(sector_el)
...     if counter_R_el[item.region] > 1 and counter_S_el[item.sector] > 1:
...         if sum_unpack <= budget:
...             unpack.append(item)
... 
>>> 
>>> for item in unpack:
...    logging.error(item)
... 
ERROR:root:Item(region='A', sector='3', name='A30', budget=4500.0, target=1.0, performance=0.02997731987752)
ERROR:root:Item(region='A', sector='1', name='A29', budget=4500.0, target=1.0, performance=0.02997731987752)
ERROR:root:Item(region='A', sector='1', name='A27', budget=4500.0, target=1.0, performance=0.02997731987752)
ERROR:root:Item(region='A', sector='5', name='A26', budget=4500.0, target=1.0, performance=0.02997731987752)
ERROR:root:Item(region='A', sector='3', name='A25', budget=4500.0, target=1.0, performance=0.02997731987752)
ERROR:root:Item(region='A', sector='1', name='A13', budget=25000.0, target=25.0, performance=0.00749432996938)
ERROR:root:Item(region='D', sector='5', name='D4', budget=100000.0, target=20.0, performance=0.0413295851708)
ERROR:root:Item(region='D', sector='5', name='D3', budget=100000.0, target=20.0, performance=0.0413295851708)
ERROR:root:Item(region='D', sector='6', name='D22', budget=65190.0, target=30.0, performance=0.020332158889648923)
ERROR:root:Item(region='C', sector='2', name='C7', budget=30000.0, target=5.0, performance=0.0616135500758)
>>> 

Answer 3

I couldn't easily sort through your code. if counter_R_el >= 1 or counter_S_el >= 1: just can't work, you can't compare a Counter() to an int(). It also looks like you continually remake/reset things in your loop suite and it became confusing.

You seem to be on the right track.

• To keep track of the number of regions and sectors collections.Counter() is a good choice.
• look at each item in the list, and check if it meets your constraints
• if removed, update the counters and the total cost

Here is what I came up with:

import collections, operator
Item = collections.namedtuple('Item', ['region', 'sector', 'name',
                                       'budget', 'target', 'performance'])

a = [Item(region='H', sector='2', name='H3', budget=7000.0, target=1.0, performance=4.0),
     Item(region='H', sector='2', name='H10', budget=35000.0, target=15.0, performance=1.0),
     Item(region='I', sector='2', name='I6', budget=50000.0, target=5.0, performance=0.40598931548848194),
     .....]

budget = 325000

# sort highest to lowest cost
a.sort(key = operator.attrgetter('budget'), reverse = True)
project_cost = sum(item.budget for item in a)
# constraint counters
region_count = collections.Counter(item.region for item in a)
sector_count = collections.Counter(item.sector for item in a)

# iterate over a copy of the list
b = a.copy()
for item in b:
    if project_cost <= budget:
        break
    # check item against constraints
    if region_count[item.region] > 1 and sector_count[item.sector] > 1:
        # remove the item from the original list 
        a.remove(item)
        # uodate the counters and cost
        region_count[item.region] -= 1
        sector_count[item.sector] -= 1
        project_cost -= item.budget

a contains the items that meet the constraints and have a total cost less than the budget.