根据各个相应元素的比例或基于第三个列表的Python中的排序2列表

Question

我正在尝试为小数点knapsack problem编写不同的实现。

为此，我有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))) 

注意，最后这两个方案不同，从最初的解决方案的情况下2双有一个相等的比例。这些解决方案将按价值进行二次排序，而第一种解决方案将保持项目与原始列表的顺序相同。

Answer 2

对于更明确的（但可以说较少Python化）溶液，在value_per_unit创建由该索引的值排序索引的列表，，并重新排列values和weights相应。

sorted_indices = [index for index, value in 
        sorted(enumerate(value_per_unit), key=lambda x: x[1])] 
values = [values[i] for i in sorted_indices] 
weights = [weights[i] for i in sorted_indices] 

print(values, weights) 

输出：

([100, 60, 120], [50, 20, 30]) 

您可以整理这件事，使用zip消除了不必要的额外循环，并具有生成表达;

values, weights = zip(*((values[i], weights[i]) for i, value in 
        sorted(enumerate(value_per_unit), key=lambda x: x[1]))) 
print(values) 
print(weights) 

其中输出;

(100, 60, 120) 
(50, 20, 30) 

注意这些最终值tuples不lists。如果你真的需要输出成为一个列表，一个简单的values, weights = map(list, (values, weights))就足够了。你甚至可以把它包装到一个班轮中，但是到那时候，可能很难跟踪发生的事情。

Answer 3

优雅的方式做，这是使与值和权重多维列表：

for i in range(len(values)): 
    values_and_weights.append([values[i], weights[i]) 
# The resulting list is [[60, 20], [100, 50], [120, 30]] 

然后，使用那种方法按重量分为关键值。

values_and_weights.sort(key=(lambda x: x[0]/x[1])) 

Answer 4

您正在遇到的问题是通过使用计算的字段在每个元件（元件I将具有计算出的值values[I]/weights[I]）引起。 为了解决这个问题并且仍然保持它非常容易理解，可以将它变成这种形式的元组：(calculated_value, (value, weight))，每个元素。

这种方法可以让您轻松阅读和理解。请看下面的解决方案：

values = [60, 100, 120] 
weights = [20, 50, 30] 
value_per_unit = [] 

for I in range(len(values)): 
    value_per_unit.append((values[I]/weights[I], (values[I], weights[I]))) 
sorted_value_per_unit = sorted(value_per_unit, key=lambda x: x[0]) 

sorted_values = [] 
sorted_weights = [] 
for I in range(len(values)): 
    (value, weight) = sorted_value_per_unit[I][1] 
    sorted_values.append(value) 
    sorted_weights.append(weight) 

print(str(sorted_values)) 
print(str(sorted_weights)) 

另外请注意，我修改了循环从原始代码：

range(values)是改变range(len(values))

由于范围将需要在列表的长度，而比名单本身。