从列表中移除符合条件的子列表

Question

我有一个项目清单，我想逐一删除从最后一个项目到第n个项目，直到它达到总预算值为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)]

除了总价值之外，我还有其他两个条件来确定该物品是否应该移除。

首先，在删除该物品后，仍然至少保留一个在列表中表示相同地区的列表。

其次，在删除该物品后，仍然至少保留一个代表相同部门的物品。

例如，我可以删除最后一个项目，因为它代表区域“A”，并且还剩下5个代表区域“A”的项目。同时它代表部门“3”，还剩下3个代表部门“3”的项目。

这种删除和检查会重复进行，直到达到至少325,000的删除预算。

我写了这段代码，但我无法得到我需要的结果。请帮我纠正它。

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

这是我的代码得到的结果，item-25仍然被删除了，但它不应该被删除。

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)

项目名称为“A12”的第25项即使我们还有预算可以削减也不能删除，因为如果删除它，就不会再有代表区域“A”的项目了，依此类推。

解决方案应该是：

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)]

谢谢您提前帮助。

- Dini KF

---

命名元组的一个好处是你可以使用点符号访问属性，而不必使用索引 - 例如i = Item(...); i.budget。 - wwii

if counter_R_el >= 1 or counter_S_el >= 1: 当我运行它时会抛出 TypeError - 它正在尝试将 Counter() 与 int() 进行比较 - 这是你的实际代码吗？ - wwii

Answer 1

当我实际运行它时，我发现了一些其他问题，因此更新答案：

• 内部的 for item in sorted_KP 使用与外部循环相同的 item 计数器并覆盖它 - 总是尝试删除最后一个 A30 项
• 当在内部循环中切换到 item2 时，我还必须反转外部循环顺序（即从最后一行开始删除）。
• 区域/扇区计数器比较不正确，导致 TypeError: unorderable types: Counter() >= int() - 需要选择匹配项的区域或扇区内特定计数
• 合并了我之前的答案：您需要使用 and 而不是 or 来连接您的两个额外条件
• 合并了 @wwii 的评论 - 确实需要将计数器比较改为 > 1，而不是 >= 1

实际测试的代码：

>>> 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)
>>> 

- Dan Cornilescu

---

另外，条件应该是> 1而不是>= 1吗？ - wwii

Answer 2

假设您使用的是Python 2，因为您在使用print时没有加上()。

请查看修改后代码中的注释：

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

我的解决方案：

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)

- acw1668

---

非常感谢，这真的对我很有帮助......还有你的笔记^^d。 - Dini KF

Answer 3

我无法轻松地浏览您的代码。if counter_R_el >= 1 or counter_S_el >= 1: 是行不通的，您不能将Counter()与int()进行比较。此外，看起来您在循环套件中不断重新制作/重置things，这使得代码变得混乱。

您似乎已经走上了正确的道路。

• 为了跟踪区域和部门集合的数量，使用collections.Counter()是一个不错的选择。
• 查看列表中的每个项目，并检查它是否符合您的约束条件
• 如果删除，则更新计数器和总成本

以下是我想出的内容：

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 包含符合约束条件且总成本低于预算的项目。

- wwii