Sortuj 2 listy w Pythonie na podstawie proporcji poszczególnych odpowiednich elementów lub na podstawie trzeciej listy

Question

Próbuję napisać różne implementacje dla ułamkowego knapsack problem.

Do tego mają 2 tablic:

1. wartości
2. Ciężarki

Wartość elementów [n] odpowiada naciskowi elementów [n]. Tak więc możemy obliczyć value_per_unit jak:

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

teraz potrzebujemy 2 tablice (wartości i wagi) mają być sortowane według tablicy value_per_unit

np Jeśli

• wartości = [60, 100, 120]
• masy = [20, 50, 30]

Następnie

• values_per_unit = [3,0, 2,0, 4,0]

• więc values_per_unit_sorted będzie [2,0, 3,0, 4,0]

potrzebne wartości i wagi tablice do:

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

Czy istnieje sposób, aby to osiągnąć za pomocą prostych funkcji lambda?

mogę jeszcze zrobić coś takiego, ale wydaje się wysoce nieefektywne każdym czasie muszę dostęp do następujących elementów:

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

Answer 1

W jednym wierszu:

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

---

Aby wyjaśnić : Najpierw spakuj listy, aby je sparować.

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

Następnie sortuj według ilorazu wartości do wagi.

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

Wreszcie, rozpakuj je z powrotem na osobne listy.

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

---

Alternatywą jest skonstruowanie krotki wyraźnie zawierające jako stosunek pierwszego elementu.

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

Ten pierwszy wydaje się być nieco szybszy w niektórych szybkich testach. Jeśli szukasz optymalnego algorytmu, prawdopodobnie będziesz musiał rozwinąć rzeczy, a rozwiązanie nie będzie tak zwięzłe.

I zająć się komentarz z @TomWyllie, jeśli masz już listę wskaźników, można użyć:

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

Zauważ, że te dwa ostatnie rozwiązania różnią się od początkowego roztworu w przypadku, gdy dwie pary mieć równy stosunek. Rozwiązania te będą sortować drugorzędnie według wartości, podczas gdy pierwsze rozwiązanie zachowa elementy w tej samej kolejności, co oryginalna lista.

Answer 2

Dla bardziej wyraźne (choć zapewne mniej pythonic) rozwiązania, tworzyć listę indeksów, posortowanych według wartości w tym indeksie wvalue_per_unit i uporządkować values i weights odpowiednio.

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) 

Wyjścia:

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

Można to posprzątać, eliminując niepotrzebne dodatkowe pętle za pomocą zip iz ekspresją generatora;

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) 

Które wyjścia;

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

Uwaga te wartości końcowe są tuples nie lists. Jeśli naprawdę potrzebujesz wyjścia do listy, wystarczy prosty values, weights = map(list, (values, weights)). Możesz nawet owinąć to w jedną liniówkę, chociaż w tym momencie prawdopodobnie trudno jest śledzić to, co się dzieje.

Answer 3

elegancki sposób to zrobić, to zrobić listę wielowymiarową z wartościami i gramaturach:

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

Następnie użyj metody sortowania o wartości podzielona przez masę jako klucz.

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

Answer 4

Problem masz jest przyczyna za pomocą pola obliczeniowego w ciągu każdego elementu (elementu będę miał obliczoną wartość values[I]/weights[I]). Aby rozwiązać ten problem i nadal bardzo łatwo go zrozumieć, można przekształcić go w krotkę tego formularza: (calculated_value, (value, weight)), dla każdego elementu.

Takie podejście ułatwia czytanie i zrozumienie.Spójrz na następujące rozwiązanie:

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

Należy również pamiętać, że zmodyfikowane pętlę z oryginalnego kodu:

range(values) była zmiana do range(len(values))

Ponieważ zakres musiałaby długość listy, raczej niż sama lista.