根据各个对应元素的比例或基于第三个列表,在Python中对2个列表进行排序

Question

我正在尝试为分数背包问题编写不同的实现.

为此我有2个数组:

1. 值
2. 权重

元素值[n]对应于元素权重[n].所以我们可以将value_per_unit计算为:

for I in range(values):
    value_per_unit.append(values[I]/weights[I])
value_per_unit.sort()

我现在需要根据value_per_unit数组对2个数组(值和权重)进行排序

例如:如果

• 值= [60,100,120]
• 重量= [20,50,30]

然后

• values_per_unit = [3.0,2.0,4.0]

• 所以values_per_unit_sorted将是[2.0,3.0,4.0]

我需要值和权重数组成为:

• values_sorted = [100,60,120]
• weights_sorted = [50,20,30]

有没有办法使用简单的lambda函数实现这一目的？

我仍然可以做这样的事情,但每次我需要访问元素时效率都非常低:

weights[(value_per_unit_sorted.index(max(value_per_unit_sorted)))]

Answer 1

在一行中:

values, weights = zip(*sorted(zip(values, weights), key=lambda t: t[0]/t[1]))

解释:首先,压缩列表以配对它们.

pairs = zip(values, weights) 
# [(60, 20), (100, 50), (120, 30)]

然后,按值与权重的商进行排序.

sorted_pairs = sorted(pairs, key=lambda t: t[0]/t[1]) 
# [(100, 50), (60, 20), (120, 30)]

最后,将它们解压缩回单独的列表中.

values, weights = zip(*sorted_pairs)
# (100, 60, 120), (50, 20, 30)

另一种方法是构造明确包含比率作为第一个元素的元组.

ratios, values, weights = zip(*sorted((v/w, v, w) for v, w in zip(values, weights)))

在一些快速测试中,前者似乎稍快一些.如果您正在寻找最佳算法,那么您可能需要展开一些内容,解决方案也不会那么简洁.

要解决@TomWyllie的评论,如果您已经有比率列表,您可以使用:

ratios, values, weights = zip(*sorted(zip(ratios, values, weights)))

注意,最后两个解决方案与两个具有相等比率的情况下的初始解决方案不同.这些解决方案将按值排序,而第一个解决方案将使项目保持与原始列表相同的顺序.