根據各個相應元素的比例或基於第三個列表的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))

由於範圍將需要在列表的長度，而比名單本身。